점근 시간 복잡도 (쎄타)

Question

나는 다음과 같은 재귀 함수의 점근 시간 복잡도를 분석하기 위해 요청을받은 : 내가 증명할 수 있었다

for-all k ≥ 1: 
T(n) = n + T(n/2) + T(n/4) + T(n/8) + .... + T(n/2^k) 

:
T(n) = O(n⋅log n) 및 T(n) = Ω(n),
그러나 나는 더 엄격한 경계 (Big Theta)를 찾고있다. 모든

Answer 1

첫째 :
나는 "를위한 모든 K> = 1"이런 식으로 이해 : k = 1에 대한 k = m2m-1 ≤ n ≤ 2m에.
이렇게 기본으로 m = log₂(n)이 성립합니다.

 
T(n) = n + Σk=1,...,m T(n/2k) 
    = n + T(n/2) + Σk=2,...,m T(n/2k) 
    = n + n/2 + 2⋅Σk=2,...,m T(n/2k) 
    = ... 
    = n + Σk=1,...,m k⋅n/2k 
    = n + n⋅Σk=1,...,m k/2k 
    = n + n⋅(2 - 2-mm - 21-m) 
    ≤ n + 2⋅n 
    = 3n 

그래서 T(n)이 Θ(n)에 있습니다

내 계산에서보세요.

알림 :
으로 Σk=1,...,m k/2k을 근사 할 수도 있습니다.
여기에 limm → ∞s(m) = 2도 있습니다.