Solve the recurrence tn tn2 log2 n such that t1 0 Assume

Solve the recurrence t(n) = t(n/2) + log_2 n, such that t(1) = 0. Assume in your solution that n is a power of 2, that is, n = 2^m so m = log_2 n. Verify that your answer in (a) is correct using a proof by mathematical induction, namely perform induction on the variable m. If two positive integers n_1 and n_2 have .N_1 and N_2 decimal digits, respectively, then computing their product n_1 n_2 using the grade school multiplication algorithm has time complexity O(N_1 N_2). For a given positive integer n, what is the O() time complexity of computing n^n, that is, n to the power n ?

Solution

As n is a perfect power of two (that is, n = 2k), you can rewrite recurrence as

T(2^k) = T(2^k-1) + k

Let\'s define a new recurrence S(k) = T(2^k). Then we get that

S(k) = S(k - 1) + k

If we expand out this recurrence, we get that

S(k) = S(k - 1) + k

       = S(k - 2) + (k - 1) + k

       = S(k - 3) + (k - 2) + (k - 1) + k

        = S(k - 4) + (k - 3) + (k - 2) + (k - 1) + k

...

         = S(0) + 1 + 2 + 3 + ... + k

         = S(0) + (k²)

Assuming S(0) = 1, then this recurrence solves to (k2).

Since S(k) = T(2^k) = T(n), we get that T(n) = (k²) = (log² n).