[18-알고리즘]점근적 분석(Asymptotic Analysis)에 대한 예제문제 풀이

1. For the functions, 4^n and 2^n, what is the asymptotic relationship between these functions? Select all that apply.

(a) 4n = O(2n)
(b) 4n = Ω(2n)
(c) 4n = Θ(2n)

[풀이]

4^n은 2^2n이다. 이는 2^2n >= c2^n이다. (c는 c>0인 양의 상수이다.)

따라서 4^n이 2^n보다 빠르게 증가하는 것을 알 수 있다. 그래프의 개형은 다음 위의 그림과 같다. (그래프는 n>0에서 형성된다.)

f(n) = 4^n, g(n) = 2^n이라고 하자. 

f(n) >= cg(n)인 4^n >= c2^n 관계가 성립한다.

따라서 점근적 하한선을 표시하는 Ω-표기인 (b) Ω(2n)가 답이다.