i have a problem with understanding this section of a book named : Computer science in distilled
my problem is when it test O(n log n) with 10x input, the result i get from fraction of 10nlog(10n)/nlog(n) is 10 but the book says it's 34. this is my solution
I think you are using log10 10, not log2 10 as from the book
Normally I think we just care about the big numbers(10 or 30 or 100), and probably use the exponent of 2(there are a lot of the algos that involves binary staff, so sometimes it is better use 2)
Your solution is right. The book is wrong. If the running cost of an input of size n is nlgn, then increasing the input size by T (in your case T=10) will incur in a running cost of Tnlg(Tn), giving a cost increase factor of Tnlog(Tn)/(nlgn), which, as you pointed out, tends to T as n → ∞.
Note however that lg2(1000) ≃ 10. Therefore, n will have to be much greater than 1000 before you can neglect the lg2(10)/lg2(n) factor. So, in general, the increase factor will be O(T), which is ok because we are dealing with big-O quantities from the very beginning.
