Question

int fun(int n) {
int count=0;
for(int i = n;i>0; i/=2)
for(int j=0; j <i; j+)
count += 1;
return count;
What is the run time complexity of the above code?
Pick one of the choices
OOO
On
On log n)
on)
On logdog n))
None of the above
Clear selection​

Answer 1

Answer:

O(n) is the right answer

Explanation:

In this program value of n is passed to function and the functions runs 2 for loop. 1st runs from n to 0 and the inner loop runs from 0 to i and whenever the control comes to the inner loop the count is incremented by 1.

For the given value of n, the inner loop runs “ n + n/2 + n/4 +….+1 “. The same applies for value of n.

To calculate the time complexity, we need to use T(n) = O (n + n/2 + n/4 +…+1)

which is equal to O(n).

Answer 2

Given:

int fun(int n)

{

   int count = 0;

   for (int i = n; i > 0; i /= 2)

       for (int j = 0; j < i; j++)

           count += 1;

   return count;

}

Answer:

O(n)

Explanation:

Every time the value of i gets divided by 2 and because of that, the value of j will get decrease after each iteration of i.

Value of i          Values of j

      n                  0 - (n-1) times

     n/2               0 - (n/2 - 1) times

     n/4               0 - (n/4 - 1) times

       .

       .

       .

       1

T(n) = O(n + n/2 + n/4 + … + 1) = O(n)

Let n = 10

i           j

10      0 - 9

5       0 - 4

2       0 - 1

The value of j also gets decreased in order on n/2 forming GP and therefore we get O(n).