retagged by
414 views
1 votes
1 votes

retagged by

1 Answer

Best answer
2 votes
2 votes

Here we have to look at the total iterations that take place to check the running time  - 

The outer i will change as N , N/2 , N/4 ,...

the inner j will loop equal to the value of i.

thus Total iterations = n + n/2 + n/4 +....

Now use geometric mean = a * (1 - r^k) / (1 - r). 

                                     = N * (1 - (1/2) ^ logn ) / (1 - 1/2)  = 2n - 2.                 

 [ k = total no of terms = logn , as N is continuously being divided by 2]

Thus T(n) = O(n)

edited by

Related questions

0 votes
0 votes
1 answer
1
akash.dinkar12 asked Apr 21, 2017
504 views
Can any algorithms exist which take less than O(1) time????
0 votes
0 votes
1 answer
2
Aspi R Osa asked Dec 14, 2015
1,509 views
Consider a set of 20 elements.To find maximum and minimum element in the given set, the minimum number of comparisons required is _________? (using DAC Max-Min algorithm)...
0 votes
0 votes
1 answer
4
Overflow04 asked Oct 9, 2022
407 views
how O($n^{2}$) in the last.(in the given solution).