educative.io

Educative

Time Complexity Challenge 4 Solution Review

Solution
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.
Thanks

2 Likes

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?