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;
}
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).
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments