Big O notation: Difference between revisions
Jump to navigation
Jump to search
(Created page with "<math>x^{a+b}</math>") |
No edit summary |
||
| Line 1: | Line 1: | ||
<math> | |||
:<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>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) : 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> | |||
Revision as of 00:36, 10 September 2014
- [math]\displaystyle{ \Theta(g(n)) = {f(n) : there exist positive constants c1,c2 and n0 such that 0\lt =''c''\lt sub\gt 1\lt /sub\gt *g(n) \lt = f(n) \lt = c2*g(n) for all \gt = n0 } }[/math]
- [math]\displaystyle{ O(g(n)) = {f(n) : there exist positive constants c1,c2 and n0 such that 0\lt =''c''\lt sub\gt 1\lt /sub\gt *g(n) \lt = f(n) \lt = c2*g(n) for all \gt = n0 } }[/math]
- [math]\displaystyle{ \Omega(g(n)) = {f(n) : there exist positive constants c1,c2 and n0 such that 0\lt =''c''\lt sub\gt 1\lt /sub\gt *g(n) \lt = f(n) \lt = c2*g(n) for all \gt = n0 } }[/math]
- [math]\displaystyle{ o(g(n)) = {f(n) : there exist positive constants c1,c2 and n0 such that 0\lt =''c''\lt sub\gt 1\lt /sub\gt *g(n) \lt = f(n) \lt = c2*g(n) for all \gt = n0 } }[/math]