HW#02 : N개의 배열을 이분 검색을 할 때 시스템 스택의 깊이는?

n개의 Array를 Binary Search(Divide and Conquer Approach)할 때 System Stack Depth는 얼마인가?

예를 들어 생각해 보면, "1, 2, 3, 4, 5, 6, 7, 8, 9"에서 9를 찾는다고 가정해 보자. 각 Step 마다 n/2 만큼 감소하게 된다. 수식으로 표현해보면 Worst Case의 Time Complexity는 w(n) = w(2/n) + 1 이 된다. 이것은 w(n) = w(2/2^2) + 2 가 되고 다음은 w(n) = w(2/2^3) + 3 형태가 된다. n을 2^x 로 놓으면 w(n/2^x) + x 에서 w(n) = w(2^x/2^x) + logn 이 된다. w(2^x / 2^x)는 1이 되고 결국 1 + logn 이 된다. 그래서 System Stack Deapth는 1 + logn 이 된다.