TADM2E 2.42

From Algorithm Wiki
Revision as of 17:22, 17 December 2019 by Manish.khkr (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Change the assumptions of the proof.

The paper mentioned is "S. Skiena. Encroaching lists as a measure of presortedness. BIT, 28:775-784, 1988."


Other solution :

$ O(nlog(√n)) $ and $ O(nlog(n)) $ belongs to same class of function with respect to Big O notation. There is no difference between them other than a constant factor.


$ \lim_{x\to\infty} (nlog(√n)) / (nlog(n)) $ = $ \lim_{x\to\infty} 1/2*(nlog(n))/(nlog(n)) $ = $ 1/2 $