64 votes 64 votes Consider the following segment of C-code: int j, n; j = 1; while (j <= n) j = j * 2; The number of comparisons made in the execution of the loop for any $n > 0$ is: $\lceil \log_2n \rceil +1$ $n$ $\lceil \log_2n \rceil$ $\lfloor \log_2n \rfloor +1$ Algorithms gatecse-2007 algorithms time-complexity normal isro2016 + – Arjun asked Jul 6, 2016 • edited Nov 22, 2017 by kenzou Arjun 37.6k views answer comment Share Follow See all 24 Comments See all 24 24 Comments reply Show 21 previous comments Abhrajyoti00 commented Nov 5, 2022 reply Follow Share @Nisha Bharti Yes, you are right, Actually answer is $\lfloor \log_2 n \rfloor + 2$ if we even include the exit condition. But here the options don't have $2$ at last, which means that we don’t need to calculate the exit condition. Thus the answer is Option D) $\lfloor \log_2 n \rfloor + 1.$ 1 votes 1 votes Saqlaini commented Sep 18, 2023 reply Follow Share What's the difference between option A.) & D.) 0 votes 0 votes ꧁༒☬ĿọŗԀ 🆂🅷🅸🆅🅰☬༒꧂ commented Jan 2 i edited by ꧁༒☬ĿọŗԀ 🆂🅷🅸🆅🅰☬༒꧂ 20 hours ago reply Follow Share @Saqlaini take i/p and check for D option u will get lesser value as we are taking floor and in Op A we will get higher value as ans for any i/p. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes due to the line "in the execution of the loop" the answer is D. if total comparisons were asked then it will be floor (logn) +2 vaibhav singh 3 answered Dec 1, 2018 vaibhav singh 3 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Answer is option D I look an array and tried to look how j changed. shashankrustagi answered Dec 8, 2020 shashankrustagi comment Share Follow See all 0 reply Please log in or register to add a comment.
–1 votes –1 votes let n=8, then then value if j that would get compaired are 1,2,4,8...number of comparison=4 upper_bound( ln8 ) +1 = 4 let n=6, then number of comparison = 3 upper_bound( ln6 ) +1 = 3 which are satisfied by option A rameshbabu answered Jul 6, 2016 • reshown Jul 6, 2016 by rameshbabu rameshbabu comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments ankit commented Jul 6, 2016 reply Follow Share I think answer should be (a) because more values of "n" are satisfied by this option. Only when "n" is power of 2, This option will not give the correct answer. 0 votes 0 votes srestha commented Sep 8, 2016 reply Follow Share @Kapil A) is not the answer. Try for n=8 0 votes 0 votes Priyanka17 commented Sep 8, 2016 reply Follow Share it would not b ln as ln is base e it would be log(n) base 2 as we are multiplynh by 2 each time so for any number expect powers of 2 ans would be upper bound(log(n) base 2)+1 0 votes 0 votes Please log in or register to add a comment.