Big O notation

From Algowiki
Jump to: navigation, search
[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]\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 \gt 0[/math], there exists ac constant [math]n_0 \gt 0[/math] such that [math]0 \le \; f(n) \lt cg(n)[/math] for all [math]n \ge \; n_0 \}[/math]

Anots.png