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