What are the asymptotic upper and lower bounds for T(n) = 2T(n/2) + n lg lg n?
-
23-10-2019 - |
سؤال
The recurrence relation
T(n) = 2T(n/2) + n lg lg n
(where lg is logarithm to base 2) can be solved using the master theorem but I am not very sure about the answer. I have found my answer but am not mentioning it here in order to prevent information cascades. Please help me find the big O and Ω for above.
المحلول
None of the 3 cases in the master theorem apply for
T(n)=2 T(n/2) + n log(log n)
(With arbitrary base, it doesn't really matter)
Case 1: f(n)=n log(log n) is 'bigger' than nlog2 2=n1
Case 2: f(n) does not fit n logk(n)
Case 3: f(n) is smaller than n1+e
U(n)=2 U(n/2) + n log n
L(n)=2 L(n/2) + n
You can show that: U(n) >= T(n)
and L(n) <= T(n)
. So U gives a upper bound, and L a lower bound for T.
Applying the master theorem for U(n), gives
Case 2: f(n)=n log n=Θ(n1 log1 n) thus U(n)=Θ(n log2 n)
Applying the master theorem for L(n), gives
Case 2: f(n)=n =Θ(n1 log0 n) thus L(n)=Θ(n log n)
Because L(n)<=T(n)<=U(n)
it follows that T(n)=O(n log2 n) and T(n)=Ω(n log n)
Also, note that O(log2n)=O((log n)/log 2)=O((log n) * c)=O(log n).