Growth of functions - Finding time complexity

 

Find the time complexity of code-

(A)
for (i = 1; i <= n; i++)
{

   printf("Hello");
}

Ans

Time Complexity: is number of operations
In this code, i will take the value from 1 to n.
i = 1, print "hello"
i = 2, print "hello"
i = 3, print "hello"
...
...
i = n, print "hello"

So, the code will print "hello" exactly n times. Time complexity is O(n)

(B)
for(i = 1; i <= n; i++)
{
  for(j = 1; j <= n; j++)
  {
    printf("Hello");
   }
}

Ans

In this code,

i	j
1	1, 2, 3, ......, n
2	1, 2, 3, ......, n
3	1, 2, 3, ......, n
.....	......
.....	......
n	1, 2, 3, ......, n

means it will print "hello" for every j value. 

so j value is 1 to n, for every, i value. i value is from 1 to n. 

so, we have n*n operations. Time Complexity is O(n^2).

(C)
for(i = 1; i <=n; i++)
{
  for(j = 1; j <=i; j++)
  {
    printf("Hello");
   }
}

Ans

In this code

i	j
1	1
2	1, 2
3	1, 2, 3
.....	......
.....	......
n	1, 2, 3, ......, n

means it will print "hello" for every j value. 

so, j values sum equal to

Sum = 1 + 2 + 3 + ...  + n = (n(n+1))/2

Sum = (n^2 + n)/2 = O(n^2)          (We remove constants and lower-order term.)

(D)

for(i = 1; i <= n; i++)

{ 

  for(j = 1; j<= n; j = j*2)

  {

    printf("Hello");

   }

}

Ans

In this code,

i	j
1	1, 2, 4, ..., k
2	1, 2, 4, ..., k
3	1, 2, 4, ..., k
.....	......
.....	......
10	1, 2, 4, ..., k

2^k <= n

After every j's value, the code will print "hello". 

so, # of operations is n*k          [k = log n]

It means that time complexity is O(n log n).

(E)

for(i = 0; i <= n; i = i*2)

{

  for(j = 0; j <= n; j = j*2)

  {

     printf("Hello");

  }

}

Ans

In the previous question, we have seen that j = j*2 derives time complexity log n.

So, in this question, i value is from 1 to n and i = i*2, and in the nested loop j value is from 1 to n and j = j*2. 

So, the code's time complexity becomes O((log n)^2).

(F) 

for(i = 0; i <=n; i = i*2)

{ 

   for(j = 1; j <= i; j = j*2)

    {

      printf("Hello");

    }

} 

Ans

i	j
2^0	2^0
2^1	2^1
2^2	2^2
.....	......
.....	......
2^m	2^m

Here 2^m is very close to or equal to n

Time Complexity = 2^0 + 2^1 + 2^2 + ..... + 2^m 

                               = (2^(m+1) - 1)/ (2 - 1)

                               = 2 * 2^m - 1

                               = 2n - 1

                               = O(n)