Why is the correct answer marked O(nlog(n)) instead of O(nlog3(n))?

Coderust · July 27, 2020, 2:24pm

A reader sent us the following feedback:

Hi, The answer of the challange is marked as O(nlogn) in the quiz.But the real correct answer is O(nlog3n), This answer is also given in the solution review part of the challange. Therefore I believe, the answer part of the challange should be updated. Thanks.

FatimahAbdullah · December 17, 2019, 10:39am

Hi Gencer,

This is Fatimah Abdullah from Educative. Thank you for reaching out to us!

In response to your feedback, your observation is absolutely correct! The reason we have mentioned $O(nlog_3(n))$ instead of $O(nlog_3(n))$ is that these Big-Oh notations are equivalent . We can say that: $log_3(n) \approx 3log(n)$

In the Big-Oh analysis, we ignore any constant multipliers. Therefore, $O(log(n)) = O(log_3(n))$ . This is a general rule for any degree x of the logarithm. I hope this explanation helps!

Thank you for reaching out to us with your feedback! If you have any further queries or concerns, please let us know.

Best Regards,
Fatimah Abdullah | Developer Advocate
Educative