Redirected
edited by
1,167 views
1 votes
1 votes

  1. O($n^2$)
  2. O(n)
  3. O(nlogn)
  4. O($n(logn)^2$

 

edited by

1 Answer

0 votes
0 votes
When i = n , inner query runs for n times ,

now i = n/2 inner query runs n/2 times ,

now i = n/4 inner query runs for n/4 times ,

So the total number of steps the inner query would run is

n + n/2 + n/4 + n/8 + n/16 + ....... for exactly log(n) times .

 take n common

n(1+1/2+1/4+1/8+1/16.... ) = n (2 - 1/2^(logn))  = n (2 - 1/n) , lets take  n approaches infinity ,

1/n approaches 0.

Therefore , complexity = O(2n) = O(n)

Related questions

2 votes
2 votes
0 answers
2
3 votes
3 votes
0 answers
3
aaru14 asked Nov 23, 2017
444 views
https://gateoverflow.in/?qa=blob&qa_blobid=6856287731579574233someone plz tell ??
1 votes
1 votes
2 answers
4
Shivi rao asked Nov 8, 2017
1,146 views
Consider an array contain n distinct elements. In array till ‘i’ location element are in increasing order and after ‘i’ location all elements are in decreasing or...