[CLRS] SUMMARY OF EXERCISE

1.2-2

같은 머신에서 각각의 알고리즘을 실행한다고 가정했으니 프로그램의 동작시간을 계산하는 식 (필요연산횟수/단위시간당처리연산개수)에서 분모는 같다고 생각하면 분자만 비교해보면 된다. 그래서 다음과 같은 부등식만 계산해서 최대 n을 찾으면 된다.

$$n<8\log{n}$$

n=1,2,3... 처럼 순차적으로 넣어서 답을 구할 수도 있지만 binary search를 사용하면 손으로 계산 시 조금 더 빠르게 계산할 수 있다.

그림 1, 그림 2(출처: https://www.quora.com/How-can-I-solve-n-8-log_-2-n)

어떤 방법을 썼든지 간에 답은 n=43인 것을 확인할 수 있다.