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 Rajnish Kumar 1 commented Jan 17, 2018 reply Follow Share @ Bikram Sir I think (log n)2=(log n)*(log n) and log2n=log(log n) Please verify this! 0 votes 0 votes Verma Ashish commented Oct 26, 2018 i edited by Verma Ashish Sep 21, 2019 reply Follow Share ...https://gateoverflow.in/42025/doubt-on-logarithms 0 votes 0 votes Ashwani Kumar 2 commented Sep 21, 2019 reply Follow Share i=2*i is not inside while loop? 0 votes 0 votes Verma Ashish commented Sep 21, 2019 reply Follow Share It is inside outer while looop and outside of inner while loop..:) 0 votes 0 votes 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 Show 13 previous comments 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.