0 votes 0 votes Find the time complexity of the function function( int n) { int i=1; while( i<n) { int j=n; while( j>0) j=j/2; i=2*i; } } $O(\log n)$ $O(n^2 \log n )$ $O(\log 2 n)$ $O( \log n^2 )$ Algorithms tbb-algorithms-2 + – Bikram asked May 26, 2017 • edited Aug 20, 2019 by Counsellor Bikram 1.0k views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments Ashwani Kumar 2 commented Sep 21, 2019 reply Follow Share Yeah correct... I mistakenly thought it inside may be because of indentation...in that case answer is O(logn) right? 0 votes 0 votes Verma Ashish commented Sep 21, 2019 reply Follow Share Yes.. If both statements will be inside inner while loop then O(logn). But here O(log²n) is correct.. 0 votes 0 votes Ashwani Kumar 2 commented Sep 21, 2019 reply Follow Share Yes 0 votes 0 votes Please log in or register to add a comment.
Best answer 1 votes 1 votes here int the code while(j>0) j=j/2;//log n time i=2*i // log n time so O( log n * log n)=O(log2 n) as (log n)k = logk n. Like, x = log n, then x2 = (log n)2 = log n * log n = log2n. Bikram answered May 26, 2017 • selected Aug 16, 2019 by Bikram Bikram comment Share Follow See all 16 Comments See all 16 16 Comments reply shraddha priya commented May 31, 2017 reply Follow Share @bikram Sir, option C has been marked wrong for me in the test and instead the answer is given as 3. 0 votes 0 votes Bikram commented May 31, 2017 reply Follow Share Now it is fine, re-solved the issue . I think your marks will increase now, Option C is correct answer . 1 votes 1 votes Harsh181996 commented May 31, 2017 reply Follow Share Sir, the syntax is very confusing in the options , I got the answer as (log(n))^2 ,and I thought answer D) meant the answer that I got.I thought option C) meant log(2n). Sir if you could make the options clearer it would be great :) 1 votes 1 votes shraddha priya commented May 31, 2017 reply Follow Share The options are clear I think. (log n)^2 = log n * log n = log 2n So it's option C. 0 votes 0 votes Harsh181996 commented Jun 1, 2017 reply Follow Share but my question is how is log n * log n = log (2n) ? 1 votes 1 votes shraddha priya commented Jun 1, 2017 reply Follow Share My bad. yes none of the options are equal to (log n)^2. 1 votes 1 votes Bikram commented Jun 1, 2017 reply Follow Share @harsh , Sorry for my stupid mistake again :) corrected it now .. Your answer was correct . @shraddha , log n * log n = log2n. And (log n)2 = ( log2 n) . Thanks for pointing it out. 0 votes 0 votes sethi commented Oct 29, 2017 reply Follow Share @Bikram Sir how the while loop will execute logn times ? i have a doubt it will be executed in the following manner int j = n, j/2+j/4+j/8+...... = n/2+n/4+n/8+.... = n(1/2+1/4+1/8+....) = n.1 = O(n).. i evaluated in this way is it correct? 1 votes 1 votes Verma Ashish commented Oct 28, 2018 reply Follow Share @Bikram how log²n=(log n)² ??? log²n is LogLogn where as (logn)² is logn*logn. 0 votes 0 votes Verma Ashish commented Oct 28, 2018 reply Follow Share My misconception regarding this got cleared after seeing this question-- https://gateoverflow.in/42025/doubt-on-logarithms Thanks to GO team 0 votes 0 votes Priyansh Singh commented Oct 19, 2019 reply Follow Share $(logn)^2 = (logn)(logn)$ and $(log^2n) = (loglogn)$ Isn't it? 1 votes 1 votes ABHIMANYUSINGH commented Oct 20, 2019 reply Follow Share (log n) ^2 =log n * log n log ^2 n =log log n 0 votes 0 votes Verma Ashish commented Oct 20, 2019 reply Follow Share @ABHIMANYUSINGH @Priyansh Singh $(\log n)^2=\log n\times\log n=\log^2n$ 0 votes 0 votes ABHIMANYUSINGH commented Oct 20, 2019 reply Follow Share Ok if u r saying : (log n)^2 =log n*log n = log^2 n then please tell me log log n =?? 0 votes 0 votes Verma Ashish commented Oct 20, 2019 reply Follow Share $\log \log n$ is simply $\log(logn)$, nothing else. 0 votes 0 votes ABHIMANYUSINGH commented Oct 20, 2019 reply Follow Share NO ........ u will check in class 11 or 12 it is given (log n) ^2= log n * log n log ^2 n= log log n 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes consider n=8 i=1 ...given j=8 inner while loop j= 4 , 2 , 1 and i= 2, 4 , 8 outer loop will break nxt time so, O(logn) shubham shende answered Nov 18, 2019 shubham shende comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes this question answer is given wrong. representation of logN*logN is not like that . royal shubham answered Apr 6, 2019 royal shubham comment Share Follow See all 0 reply Please log in or register to add a comment.