2 votes 2 votes Consider the following code . What should be the time complexity? j = n ; while (j >= 1){ for (i = 1 to j ) x = x + 1 ; j = n/2 ; } (A)O(logn) (B)O(n logn) (C)O(n ) (D)None of the above Algorithms algorithms time-complexity + – ManojK asked Jun 4, 2016 • retagged Jun 28, 2022 by makhdoom ghaya ManojK 1.7k views answer comment Share Follow See all 29 Comments See all 29 29 Comments reply shivanisrivarshini commented Jun 4, 2016 reply Follow Share Option C O(n) 0 votes 0 votes Tauhin Gangwar commented Jun 4, 2016 reply Follow Share option A & B are same plz correct the question 0 votes 0 votes ManojK commented Jun 4, 2016 reply Follow Share @shivani nopes it not O(n) . 0 votes 0 votes shivanisrivarshini commented Jun 4, 2016 reply Follow Share @ManojK what i think is initally j=n =>i gets executed n times j=n/2 =>i executes n/2 times .... n+n/2+n/4 + ..... 1 n+n/2+n/4 ..... +n/2k =>2k =n n(1+1/2+1/4+....+1/2k ) n(1* (1-(1/2)k)/1-1/2 = 2n(1-1/n) =O(n) 0 votes 0 votes ManojK commented Jun 4, 2016 reply Follow Share @shivani you need to double check the procedure .How it is working . 0 votes 0 votes shivanisrivarshini commented Jun 4, 2016 reply Follow Share @ManojK whats the answer 0 votes 0 votes ManojK commented Jun 4, 2016 reply Follow Share i will give the answer wait some time ... 0 votes 0 votes ManojK commented Jun 4, 2016 reply Follow Share @Rude Sir .Can u answer this ? 1 votes 1 votes Tauhin Gangwar commented Jun 4, 2016 reply Follow Share manoj answer is logn i m 100% sure 0 votes 0 votes rude commented Jun 4, 2016 reply Follow Share Answer is $O(n log n)$. is not? 0 votes 0 votes ManojK commented Jun 4, 2016 reply Follow Share Nopes rude sir ? 0 votes 0 votes ManojK commented Jun 4, 2016 reply Follow Share Hint :Ok see the assignment line here j=n/2 . 1 votes 1 votes shivanisrivarshini commented Jun 4, 2016 reply Follow Share @ManojK do u know the solution ??? 0 votes 0 votes Tauhin Gangwar commented Jun 4, 2016 reply Follow Share discussion is getting hot...ARJUN sir so some other experienced veteran should interfare 0 votes 0 votes rude commented Jun 4, 2016 reply Follow Share Thanks @manojK :D :D it is indeed tricky. 0 votes 0 votes ManojK commented Jun 4, 2016 reply Follow Share Stack overflow 1 votes 1 votes rude commented Jun 4, 2016 reply Follow Share hahaha.. thanks dude.. it was indeed a nice question. :D :D __/\__ keep asking. All the love. 1 votes 1 votes shivanisrivarshini commented Jun 4, 2016 reply Follow Share @ManojK simple question but tricky thank u 1 votes 1 votes ManojK commented Jun 4, 2016 reply Follow Share thank u shivani . 0 votes 0 votes srestha commented Jun 4, 2016 reply Follow Share And what answer if it is j=j/2 ? 0 votes 0 votes Tauhin Gangwar commented Jun 4, 2016 reply Follow Share srestha it would be logn 0 votes 0 votes rude commented Jun 4, 2016 reply Follow Share @srestha $O(nlogn)$ 0 votes 0 votes srestha commented Jun 4, 2016 reply Follow Share first tell me what 1+2+4-----------+n/2 +n =?? is it not G.P. series? how it's summation be O(n) or O(log n)?? 0 votes 0 votes srestha commented Jun 4, 2016 reply Follow Share @rude @tuhin chk it https://gateoverflow.in/4543/time-complexity?show=4545#a4545 same problem rt? 1+2+4-----------+n/2 +n =O(n) how?? 1 votes 1 votes rude commented Jun 4, 2016 reply Follow Share @srestha Outer loop run $O(logn)$ times, Inner loop in worst case run $O(n)$ times then what would be worst case time complexity of the algorithm? 0 votes 0 votes srestha commented Jun 4, 2016 reply Follow Share @rude it is a summation of G.P. series how do finding at most loop running n times So, worst case will be O(n)?? 1 votes 1 votes rude commented Jun 4, 2016 reply Follow Share @srestha oppps It will be $O(2n)$, then it becomes $O(n)$. dude i need a lot of learning :P Thanks srestha, you are a jem. :D 1 votes 1 votes Tauhin Gangwar commented Jun 4, 2016 reply Follow Share yes srestha...i think...i wud be o(n) u r right 1 votes 1 votes srestha commented Jun 4, 2016 reply Follow Share yes I missed it too it will be 2logn-1/(2-1) =O(n) 1 votes 1 votes Please log in or register to add a comment.
Best answer 8 votes 8 votes The only thing which you need to care is that $j = \frac{n}{2}$ this will not allow this program to terminate if $n > 1$ j = n; while (j >= 1){ for (i = 1 to j) x = x + 1; j = n/2; // If n > 1 then J will always be greater than // or equal to 1, hence this loop will not terminates. } Hence Answer will be D) None of the above Thanks @manojK rude answered Jun 4, 2016 • selected Jun 4, 2016 by ManojK rude comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Tauhin Gangwar commented Jun 4, 2016 reply Follow Share offcourse you are right now,, if it would have been j=j/2 then answer would be logn everybody committed mistake 0 votes 0 votes rude commented Jun 4, 2016 i edited by rude Jun 4, 2016 reply Follow Share @Tauhin Dude what is the addition of this series.. n + (n/2) + (n/4) + (n/8) + ............. + 2 + 1 How it can be $O(logn)$. Dude, can not you see the first term $n$ so how it can be $O(logn)$.?? 0 votes 0 votes Devshree Dubey commented Jun 4, 2016 reply Follow Share Please can you give detailed explanation of the above code. It is going above my head. Utterly confused on the explanation tat u've given. It'll be b8r if u go for line by line detailed explanation of each line of the code. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Outer while loop will run O(log n) times inner loop for each iteration of outer loop will run when j=n inner loop will run n times " j=n/2 " " " " n/2 " " j=n/4 " " " " n/4 " . . . " j=2 " " " " 1 " inner loop will total run =1+2+4+ .......+n/4+n/2+n = 1(2n -1) /(2-1) =O(2n) srestha answered Jun 4, 2016 • reshown Jun 4, 2016 by srestha srestha comment Share Follow See 1 comment See all 1 1 comment reply Tauhin Gangwar commented Jun 4, 2016 reply Follow Share sherstha dear u r getting the right series but wrong answer... 1+2+4.......2^k then for what value of k 2^k=n check it once 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes for (i=1 to j) => j=n => so runs n times =>j=n/2 so runs n/2 times =>j=n/8 so runs n/8 times So, it runs, n+n/2+n/8+n/16+.........1 Calculating it, we get O(n) times. mk_15 answered Jun 4, 2016 mk_15 comment Share Follow See 1 comment See all 1 1 comment reply srestha commented Jun 4, 2016 reply Follow Share it's a geometric series why u r not applying S= a(rn-1)/(r-1) 0 votes 0 votes Please log in or register to add a comment.