Time Complexity Challenge 4 Solution Review

There is an error when i selected the option as n log3n it showed correct and it should be but in the solution it is saying nlog2n why are we converting it to the base 2? what is the necessity?

Hello Akarsh
In terms of Big O, both n log3n and n log2n are in the same class. We converted log3n to a well known base logarithm, i.e., log2n, which is commonly used in mathematics, whereas log3n is not something you see frequently.


Hello Author,

In the below loop, why it is n/2? it should be n right? if it was j*=2 then it will be n/2.
Please can you explain.

for (int j = 1; j < n; j += 2)// O((log3 n)*(n/2))

ex: if n =100

j+=2 , will be 2,4,8,10,12 … it will not be 50, 25, 12, 6, 3… right?

Hey @Shiva_Kumar

j += 2 will iterate n/2 times.
If it was j *= 2, then it would iterate log base 2 of n times.

Course: Data Structures for Coding Interviews in C++ - Learn Interactively
Lesson: Solution Review: Nested Loop with Multiplication (Basic) - Data Structures for Coding Interviews in C++