##### What is time complexity of given function

What is time complexity of fun( )?
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;
}
(a) O(n^2)

(b) O(nlog n)
(c) O(n)

(d) O(nlog n log n)

Sumit Verma
30 Jun 2017 04:00 pm

The outer for loop iterates log n times.
For first iteration of the outer for loop, inner for loop iterates n times.
For second iteration of the outer for loop, inner for loop iterates n/2 times.
For third iteration of the outer for loop, inner for loop iterates n/4 times...

Therefore, the total number of iterations of the inner for loop or the total number of times the statement count += 1executes equals to
n + n/2 + n/4 + ... + 1 (total log n number of terms) = 2n - 1 = O(n)
Therefore, time complexity is O(n).

Tarun Kalra
30 Jun 2017 05:19 pm

n + n/2 + n/4 + ... + 1 (total log n number of terms) = 2n - 1 ? Why a factor of 2 in 2n-1. By solving with GP sum formulae I am getting only n-1 . Correct me where I have gone wrong.

Sumit Verma
30 Jun 2017 05:36 pm
Tarun Kalra
30 Jun 2017 09:06 pm

Thanksl Found where I have gone wrong.