educative.io

Not fully understanding this solution


#1

Hello,

I would think the answer for this question is n(log base 2 of n). It’s very similar to the question in Challenge 4 and that solution is n(log base 3 of n). Can someone explain why the solutions are different even though in theory they should be similar?

Thanks


#2

Hi @Wilson_So,

Thanks for reaching out!

Both the answers O(n log_2 n) and O(n log_3 n) are not wrong. O(n) just gives a tighter bound on the running time. As mentioned in the lesson, the sum += 1 line runs 1 + 2 + 4 + … + n times. That is a geometric series. The number of terms in this series is log_2(n) + 1 because the term goes from 1 to n while doubling every time. The sum of a geometric series formula says that the sum of this series is 2^{ log_2(n) + 1 } - 1 = 2.2^{log_2(n)} - 1 = 2n - 1 which is in O(n). Note that the sum of the series 2^0 + 2^1 + 2^2 + … + 2^k is 2^{k+1} - 1, as pointed out in the Wikipedia article linked from the lesson.

Also, apologies for the late response. We hope this clears the confusion. Please feel free to reach out to us if you have any other questions or comments!

— Team Educative