Difference between revisions of "TADM2E 2.42"
From Algorithm Wiki
(Recovering wiki) |
Manish.khkr (talk | contribs) |
||
| (One intermediate revision by one other user not shown) | |||
| Line 1: | Line 1: | ||
Change the assumptions of the proof. | Change the assumptions of the proof. | ||
| − | The paper mentioned is | + | The paper mentioned is "S. Skiena. Encroaching lists as a measure of presortedness. BIT, 28:775-784, 1988." |
| + | |||
| + | |||
| + | '''Other solution :''' | ||
| + | |||
| + | <math> O(nlog(√n)) </math> and <math> O(nlog(n)) </math> belongs to same class of function with respect to Big O notation. | ||
| + | There is no difference between them other than a constant factor. | ||
| + | |||
| + | |||
| + | <math>\lim_{x\to\infty} (nlog(√n)) / (nlog(n))</math> | ||
| + | = <math>\lim_{x\to\infty} 1/2*(nlog(n))/(nlog(n)) </math> | ||
| + | = <math>1/2</math> | ||
Latest revision as of 17:22, 17 December 2019
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 $
