1 votes 1 votes Find the complexity of below pseudocode. temp = 1 repeat for i=1 to n temp=temp +1; n=n/2; until n<= 1 Algorithms algorithms time-complexity + – Prakhar Garg asked Mar 18, 2019 • edited Jun 16, 2022 by Arjun Prakhar Garg 1.3k views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply Prakhar Garg commented Mar 18, 2019 reply Follow Share In the book it is given that by Master's theorem it will be O(nlogn), but by masters it should be O(n)...but if we see the code then it looks like nlogn is the correct answer 0 votes 0 votes Shaik Masthan commented Mar 18, 2019 reply Follow Share what is recurrence equation ? 0 votes 0 votes Winner commented Mar 18, 2019 reply Follow Share The recurrence equation for this will be T(n) =T(n/2)+n from master theorm.the answer will be O(n) only 0 votes 0 votes Prakhar Garg commented Mar 18, 2019 reply Follow Share T(n)= T(n/2)+n 0 votes 0 votes Prakhar Garg commented Mar 18, 2019 reply Follow Share But my doubt is, if we see the code then 'repeat' loop will run logn times and each time the inside loop runs n time...so shouldn't it be O(nlogn). 0 votes 0 votes Shaik Masthan commented Mar 18, 2019 reply Follow Share n is not constant while iteration, right? i mean by seeing repeat, we can just say log n, but how can you multiply by n due to n is also changing ? 0 votes 0 votes Winner commented Mar 18, 2019 reply Follow Share No you are getting it wrong,initially when have n,in first iteration of repeat, the for loop is executed n times ,now n is getting divided by 2 so. we getn= n/2 ,so now in second iteration ,although for loop executed n times but n has changed ,same for next iterations it happens ,hence the whole function is called again and again each time by n/2 so it is behaving like recurrence 0 votes 0 votes Prakhar Garg commented Mar 18, 2019 reply Follow Share Okay...i got it...thanks for explanation 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes So, will it be nlogn or logn? I usually get confused in these two. If you know any trick, please let me know brettlee answered Aug 20, 2020 brettlee comment Share Follow See all 0 reply Please log in or register to add a comment.