Great idea for an article. It's a good reminder that interviewers may want to drill down into a question. Just FYI, the original function is O(n log(n) + n) which is O(n log(n)). It isn't O(n). So your second version is actually quite a bit faster. Also, big-theta (Θ) is different from big-oh.
Great idea for an article. It's a good reminder that interviewers may want to drill down into a question. Just FYI, the original function is
O(n log(n) + n)
which isO(n log(n))
. It isn'tO(n)
. So your second version is actually quite a bit faster. Also, big-theta (Θ
) is different from big-oh.You're right, it's been a while since I've had to do time complexity, I'll update it.
I had to double-check myself that
n log(n)
is higher order thann
:)