Difference between revisions of "2.47"
Jump to navigation
Jump to search
| Line 6: | Line 6: | ||
'''Other solution :''' | '''Other solution :''' | ||
| − | <math> O(nlog(\ | + | <math> O(nlog(\sqrt{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. | There is no difference between them other than a constant factor. | ||
| − | <math>\lim_{x\to\infty} ( | + | <math>\lim_{x\to\infty} (nlog(\sqrt{n})) / (nlog(n))</math> |
= <math>\lim_{x\to\infty} 1/2*(nlog(n))/(nlog(n)) </math> | = <math>\lim_{x\to\infty} 1/2*(nlog(n))/(nlog(n)) </math> | ||
= <math>1/2</math> | = <math>1/2</math> | ||
Latest revision as of 19:50, 10 September 2020
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 :
[math]\displaystyle{ O(nlog(\sqrt{n})) }[/math] and [math]\displaystyle{ 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]\displaystyle{ \lim_{x\to\infty} (nlog(\sqrt{n})) / (nlog(n)) }[/math]
= [math]\displaystyle{ \lim_{x\to\infty} 1/2*(nlog(n))/(nlog(n)) }[/math]
= [math]\displaystyle{ 1/2 }[/math]
Back to Chapter 2
