빅 오 표기법

Big-O Notation

함수의 상한을 의미한다.

f(n)과 g(n)에 대하여 n>=n0인 모든 n에 대하여 |f(n)|<=c|g(n)|을 만족하는 상수 c와 n0가 존재하면 f(n)=O(g(n))이다.

빅 오메가 표기법

Big–Ω Notation

함수의 하한을 의미한다.

f(n)과 g(n)에 대하여 n>=n0인 모든 n에 대하여 |f(n)|>=c|g(n)|을 만족하는 상수 c와 n0가 존재하면 f(n)=Ω(g(n))이다.

빅 세타 표기법

Big–θ Notation

함수의 하한인 동시에 상한을 의미한다.

f(n)과 g(n)에 대하여 n>=n0인 모든 n에 대하여 c1|g(n)|<=|f(n)|<=c2|g(n)|을 만족하는 상수 c1, c2와 n0가 존재하면 f(n)=Ω(g(n))이다.