1 votes 1 votes What is the complexity of the following code? i = n while (i>=1){ for j = 1 to n x=x +1 i = i/2 } $\Theta(n)$ $\Theta( \log_2 n)$ $\Theta( n/\log_2 n)$ $\Theta( n \log_2 n)$ Algorithms time-complexity + – ManojK asked Apr 26, 2016 • edited Apr 29, 2016 by Pragy Agarwal ManojK 1.9k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 6 votes 6 votes The outer while loop runs logn times because every time n is getting divided by 2 ie {n/2 , n/4 , n/8 , ......1 } For every iteration of outer loop inner loop runs n times . Therefore the complexity is $\Theta$(nlogn) Ans : Option D. Riya Roy(Arayana) answered Apr 26, 2016 • selected Apr 26, 2016 by srestha Riya Roy(Arayana) comment Share Follow See 1 comment See all 1 1 comment reply Ram Swaroop commented Feb 10, 2020 reply Follow Share For every value of i j run 1 to n So o(n log n) d 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Both the loops are independent of each other . Inner loop always runs for n times and outer loop log₂n times . Hence complexity is : O(n log₂n) Vartika Rawat answered Jan 21 Vartika Rawat comment Share Follow See all 0 reply Please log in or register to add a comment.