Time complexity of fun()?

Question

I was going through this question to calculate time complexity.

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

My first impression was O(n log n) but the answer is O(n). Please help me understand why it is O(n).

Claudy

Answer 1

The inner loop does n iterations, then n/2, then n/4, etc. So the total number of inner loop iterations is:

   n + n/2 + n/4 + n/8 + ... + 1  
<= n * (1 + 1/2 + 1/4 + 1/8 + ...) 
 = 2n

(See Geometric series), and therefore is O(n).

Prosciutto

what about the outer loop? – Aleksandropol

@Aleksandropol The outer loop does less than O(n) iterations (it actually does O(logn)) so it doesn't affect the big-O complexity. – Prosciutto

That's what I got confused as the OP. outer loop is O(logn) and inner loop is O(n) ..so, the total time complexity is O(nlogn)...got confused here..can you help me? – Aleksandropol

@Aleksandropol The inner loop doesn't do n iterations each time, it's less. What you need is the total number of iterations it does, which is what I calculate in my answer. – Prosciutto

awesome...explanation and by the way... if anyone confused why the (1 + 1/2 + 1/4 + 1/8 + ...) became 2, it is because of infinite sum of GP and it is equal to (1/(1-r)) where r is the ratio of nth and (n-1)th term, which in our case is 1/2 so (1/(1-1/2)) = 2 and so he has written 2*n. – Varicocele

Answer 2

For an input integer n,

for i=n, j loop will run n times, then for i= n/2, j loop will run n/2 times, . . so on, . . till i=1, where j loop will run 1 time.

So,

T(n) = (n + n/2 + n/4 + n/8 + ...... + 1) 
    T(n) = n(1 + 1/2 + 1/4 + 1/8 + ..... + 1/n)                     .....(1)
let 1/n = 1/2^k

so, k = logn

now, using summation of geometric series in eq 1

T(n) = n((1-1/2^k) / 1-1/2)
T(n) = 2n(1-1/2^k)

using k = logn
T(n) = 2n(1-1/2^logn)

now for larger value of n, logn tends to infinite and 1/2^infinite will tend to 0. so, T(n) = 2n so, T(n) = O(n)

Dynamometer

Answer 3

let's have i and j table

where n = 8

i -> less than 0

j -> less than i

i	j
8	[0,7]
4	[0,3]
2	[0,1]
1	[0,0]

"i" which is outer loop is logn

Now check for "j" inner loop

[0, 7] -> b - a + 1 -> 8 -> n

[0, 3] -> b - a + 1 -> 4 -> n/2

[0, 1] -> b - a + 1 -> 2 -> n/4
[0, 0] -> b - a + 1 -> 1 -> n/n

if you see it's [n + n/2 + n/4....1] it's moving to infinity not logn times

it's infinite series right if we look closely it's GP with infinite series n[1 + 1/2 + 1/4 + .......] where (r < 1)

sum of series will gives us 2 (for GP proof you check google)

which is

n[1 + 1/2 + 1/4 + .......] -> 2n

so logn + 2n => O(n)

Vermifuge

Answer 4

For a input integer n,

the innermost statement of fun() is executed following times. n + n/2 + n/4 + ... 1 So time complexity T(n) can be written as

T(n) = O(n + n/2 + n/4 + ... 1) = O(n) The value of count is also n + n/2 + n/4 + .. + 1

The outermost loop iterates in O(logn) so it is ignored as O(n) is high

Cotidal