Question

4. [10pts Find a tight asymptotic upper bound for the function T(n) defined by the recurence relation T(2)-2 T(n) = T(n/2) + Tuv )) + n Assume that n is a power of 2

Answer 1

We expand the recursive formula and find the following

We expand the recursive formula and find the following T (n) = n + n/2 + n/4 + ... _upto log_2n - 1_terms + squareroot n/2 + squareroot n/4 + squareroot n/8 + ..._upto log *_2 - 1_terms + .. + n^1/2 + n^1/4 + ... upto log_2n - 1_terms = n times 1 - (1/2) log_2 n/1 - 1/2 + squareroot n/2 times 1 - (1/2)^log_2n/1 - 1/2 + ... + squareroot n = 2n + squareroot n + .. + squareroot n = 0 (n + squareroot n) by ignoring smaller terms
upto terms +

                 $\frac{\sqrt{n}}{2}+\frac{\sqrt{n}}{4}+\frac{\sqrt{n}}{8}+...$ upto terms +

                 ... +

                $n^{\frac{1}{2}}+n^{\frac{1}{4}}+...$ upto terms

           $=n\times \frac{1-(\frac{1}{2})^{log_2 n}}{1-\frac{1}{2}}+\frac{\sqrt{n}}{2}\times \frac{1-(\frac{1}{2})^{log_2 n}}{1-\frac{1}{2}}+...+\sqrt{n}$

            $=2n+\sqrt{n}+...+\sqrt{n}$

           $=O(n+\sqrt{n})$ by ignoring smaller terms