CODEWITHSUNDEEP
time-complexity
Dhruv K
Dhruv K

Reputation: 55

Time Complexity of the given nested loops

I have been told that the time complexity of this code is O(n),could you please explain me how is it so. The time complexity of the outer loop is log n,inner?

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;
}

Upvotes: 2

Views: 221

Answers (1)

Dakkaron
Dakkaron

Reputation: 6276

That's actually quite easy once you understand what the function does.

The inner loop basically adds i to count. So you can just reduce the code here to this:

int fun(int n) {
 int count = 0;
 for (int i = n; i > 0; i /= 2)
  count += i;
 return count;
}

So now what you have is it halves i and adds that half to count. If you keep doing that you'll end up with a number close to n. If you'd do it with an infinitely accurate float representation of i and count you will actually get exactly n (though it will take you an infinite amount of steps).

For example, let's look at n=1000, these are the steps that will be taken:

i: 500    count: 500
i: 250    count: 750
i: 125    count: 875
i: 62     count: 937
i: 31     count: 968
i: 15     count: 983
i: 7      count: 990
i: 3      count: 993
i: 1      count: 994

The 6 that are missing from count in the end are rounding mistakes at i=125/2, i=31/2, i=15/2, i=7/2, i=3/3 and i=1/2.

So you can see, the complexity of that function is almost exactly n, which certainly makes it O(n).

Upvotes: 2

Related Questions