Difference between revisions of "2.47"

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search
 
Line 6: Line 6:
 
'''Other solution :'''  
 
'''Other solution :'''  
  
<math> O(nlog(\sqrtn)) </math> and <math> O(nlog(n)) </math> belongs to same class of function with respect to Big O notation.
+
<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} (blog(/sqrtn)) / (nlog(n))</math>  
+
<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