SOME에 대하여 input data: D[1] ~ D[n]
int SOME(key)
{

for (i=1; i <= n; i++) if (D[i] == key) return i; return 0;

}
(a) Tb(n)을 도출하시오.

(b) 이 Tb(n)의 점근적 표현은?

(c) Tw(n)을 도출하시오.

(d) 이 Tw(n)의 점근적 표현은?

(e) 앞의 (b)와 (d) 결과들을 활용하면 T(n)의 점근적 하한과 점근적 상한 표현은? 




a:: 최선의 경우 D[i]==key가 동일할 경우 바로 구해지니 Tb(n) = 1

b:: 빅오메가(1)

c:: 최악의 경우 n번 모두 돌아야하니까 Tw(n) = n

d:: 빅오(n)

e:: 1<=F(n)<=n 이므로 O(n), 오메가(1)


제가 풀어본 답안인데 확인 부탁드립니다.