Estimation of Time Complexity for Given Program/Functions
1.
int count = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < i; j++)
count++;
Lets see how many times count++ will run.
When i=0, j will run 0 times.
When i=1, j will run 1 times.
When i=2, j will run 2 times and so on.
𝑁∗(𝑁−1)
Total number of times count++ will run is 0+1+2+...+ (N−1) = 2
. So, the time
complexity will be O(N2).
2.
for (int i = 1; i <= N; i= i*2)
printf(“Hello World”);
To analyse the time complexity for loop executes for i=1, i=2, i= 4, i=8 …… upto i=N
20, 21 22 23 ………….. 2k
i.e. N = 2k
k = log2 N implies Time Complexity = O (log2 N)
3.
for (int i = 1; i <= N; i= i*4)
printf(“Hello World”);
To analyse the time complexity for loop executes for i=1, i=4, i=16, i=64 …… upto i=N
40, 41 42 43 ………….. 4k
i.e. N = 4k
k = log4 n implies Time Complexity = O (log4 n)
4.
int count = 0;
for (int i = N; i > 0; i = i/2)
for (int j = 0; j < i; j++)
count++;
Think about how many times count++ will run-
When i=N, j will run N times.
When i=N/2, j will run N/2 times.
When i=N/4, will run N/4 times and so on.
Total number of times count++ will run is N+N/2+N/4+...+1= 2∗N. So, the time complexity
will be O(N).
5.
int i = N;
while (i > N) {
/* Some operation */
i = i/2; // dividing the list into two half every time, means (log2 N)
}
if we want to do some operation on the array list in which we divide the N by half every
time, or we can say that we want to access the middle element of the array list, then, in that
case, we divide the list by 2. When we divide the list by 2, then we simply write its time
complexity as O(log2 N).
6.
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j= j*2)
count++;
How many times count++ will run-
When i=1, j will run log2 N times.
When i=2, j will run log2 N times.
When i=3, j will again run log2 N times and so on.
So, the total time complexity = O (N * log2 N)