How option C is more accurate where both C and D is taking log(n) time


How can we say C is fastest when D is also executing in log(n) .


Dear Friend, in option D loop won’t terminate since it will get stuck when i will reach 0.


The last loop doesn’t terminate. Check the condition


The last loop never ends .


In option D the loop will tend to zero but it will always be greater than -1 so for loop won’t terminate.


The variable ‘i’ is an integer. Not a float.
int i=1;
i = i/2;
The value of i will be 0 now.
But the loop will never end after it reaches 0;


Many other people have given correct answers to this question, but I wanted to throw my answer in as well.

If you glance over each of the for loops quickly, it will appear as if both C and D will be log(n). However, it turns out that not only is this not true, but D will take the longest out of all the options given! This is because D will never terminate. Since we are updating our loop by dividing our index by 2, our index will ALWAYS satisfy the continue condition “i > -1”. To make D actually run in the same time as C, we need to change the continue condition to “i > 0”.


While dividing N by 2 we cannot reach less than 0 and loop ends if N becomes negative , hence this is an infinte loop so this option is having highest running time, therefore it is not correct answer.
if terminating would be n>=0 then it can be log(n).


option D will fall in infinite loop as division will always be greater than -1


option c is a pointer not multiplication


In the condition statement n is always equal to a positive number, there is no way for a positive number to ever equal a negative number when consistently divided by a positive number (2)


Its because Multiplication is faster than division.(although both C and D has log(n) complexity At university I was taught that division takes six times that of multiplication. The actual timings are architecture dependent but in general multiplication will never be slower or even as slow as division. Always optimize your code towards using multiplication if the rounding errors allow.