Time complexity Analysis

Big O 시간의 상한(최악)

g(n)<=c*f(n):asymptotic upper bound

(c:some positive real constant N:some nonnegative integer s.t. for all n>=N)

g(n) is big O of f(n)

Omega 시간의 하한(최선)

g(n)>=c*f(n):asymptotic lower bound

(c:some positive real constant N:some nonnegative integer s.t. for all n>=N)

g(n) is omega of f(n)

 

Order 시간의 평균

c*f(n)<=g(n)<=d*f(n)

(c,d:some positive real constant N:some nonnegative integer s.t. for all n>=N)

g(n) is order of f(n)

오더를 빅오로 사용하는 경우가 많습니다.

참고 사이트

https://memostack.tistory.com/57

시간 복잡도 (빅오, 빅오메가, 빅세타)