Θ, Ο, Ω notation

Θ - notation

Θ(g(n))은 어떤 프로그램의 수행시간 f(n)에 대하여 f(n)보다 같거나 작게 되는 C1*g(n)과, f(n)보다 크거나 같게 되는 C2*g(n)이 존재한다.
이것을 만족하는 C1, C2가 존재한다면 그 프로그램은 Θ(g(n))의 수행시간을 갖는다.
즉, Θ는 asymptotically tight bound를 의미한다.


Ο - notation

Ο(g(n))은 어떤 프로그램의 수행시간 f(n)에 대하여 f(n)보다 같거나 작은 C*g(n)이 성립하는 상수 C가 존재한다면, 그 프로그램은 Ο(g(n))의 수행시간을 갖는다.
즉, Ο는 upper bound를 의미한다.


Ω - notation

Ω(g(n))은 어떤 프로그램의 수행시간 f(n)에 대하여 f(n)보다 크거나 같은 C*g(n)이 성립하는 상수 C가 존재한다면, 그 프로그램은 Ω(g(n))의 수행시간을 갖는다.
즉, Ω는 lower bound를 의미한다.