Big O notation: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
No edit summary
Line 1: Line 1:


:<math>\Theta(g(n)) = {f(n) : there exist positive constants c1,c2 and n0 such that 0<=''c''<sub>1</sub>*g(n) <= f(n) <= c2*g(n) for all >= n0 }</math>
:<math>\Theta(g(n)) = \{f(n) :</math> there exist positive constants <math>c_1</math>,<math>c_2</math> and <math>n_0</math> such that <math>0\le \;c_1g(n) \le \; f(n) \le \; c_2g(n)</math> for all <math>n \ge \; n_0 \}</math>


:<math>O(g(n)) = \{f(n) :</math> there exist positive constants <math>c</math> and <math>n_0</math> such that <math>0\le \; f(n) \le \; cg(n)</math> for all <math>n \ge \; n_0 \}</math>


:<math>O(g(n)) = {f(n) : there exist positive constants c1,c2 and n0 such that 0<=''c''<sub>1</sub>*g(n) <= f(n) <= c2*g(n) for all >= n0 }</math>
:<math>\Omega(g(n)) = \{f(n) :</math> there exist positive constants <math>c</math> and <math>n_0</math> such that <math>0 \le \; cg(n)\le \; f(n)</math> for all <math>n \ge \; n_0 \}</math>


:<math>o(g(n)) = \{f(n) :</math> for any positive constant <math>c > 0</math>, there exists ac constant <math>n_0 > 0</math> such that <math>0 \le \; f(n) < cg(n)</math> for all <math>n \ge \; n_0 \}</math>


:<math>\Omega(g(n)) = {f(n) : there exist positive constants c1,c2 and n0 such that 0<=''c''<sub>1</sub>*g(n) <= f(n) <= c2*g(n) for all >= n0 }</math>
:<math>o(g(n)) = {f(n) : there exist positive constants c1,c2 and n0 such that 0<=''c''<sub>1</sub>*g(n) <= f(n) <= c2*g(n) for all >= n0 }</math>
[[File:anots.png]]
[[File:anots.png]]

Revision as of 16:03, 18 October 2014

[math]\displaystyle{ \Theta(g(n)) = \{f(n) : }[/math] there exist positive constants [math]\displaystyle{ c_1 }[/math],[math]\displaystyle{ c_2 }[/math] and [math]\displaystyle{ n_0 }[/math] such that [math]\displaystyle{ 0\le \;c_1g(n) \le \; f(n) \le \; c_2g(n) }[/math] for all [math]\displaystyle{ n \ge \; n_0 \} }[/math]
[math]\displaystyle{ O(g(n)) = \{f(n) : }[/math] there exist positive constants [math]\displaystyle{ c }[/math] and [math]\displaystyle{ n_0 }[/math] such that [math]\displaystyle{ 0\le \; f(n) \le \; cg(n) }[/math] for all [math]\displaystyle{ n \ge \; n_0 \} }[/math]
[math]\displaystyle{ \Omega(g(n)) = \{f(n) : }[/math] there exist positive constants [math]\displaystyle{ c }[/math] and [math]\displaystyle{ n_0 }[/math] such that [math]\displaystyle{ 0 \le \; cg(n)\le \; f(n) }[/math] for all [math]\displaystyle{ n \ge \; n_0 \} }[/math]
[math]\displaystyle{ o(g(n)) = \{f(n) : }[/math] for any positive constant [math]\displaystyle{ c \gt 0 }[/math], there exists ac constant [math]\displaystyle{ n_0 \gt 0 }[/math] such that [math]\displaystyle{ 0 \le \; f(n) \lt cg(n) }[/math] for all [math]\displaystyle{ n \ge \; n_0 \} }[/math]

Anots.png