ECE PhD QE CE 2013 Problem1.1 - Rhea

Problem 1.

(a) Assume the run time for some algorithm is given by the following recurrence:
$ \begin{equation} T(n) = 2T(\sqrt[]{n}) + \log n \end{equation} $ Find the asymptotic run time complexity of this algorithm. Give details of your computation.

(b) Assume functions $ f $ and $ g $ such that $ f(n) $ is $ O(g(n)) $. Prove or disprove that $ 3^{f(n)} $ is $ O(3^{g(n)}) $.

Share and discuss your solution below.

Solution 1

(a) First, let us change the variables. Let $ n = 2^{m} $, so equivalently, we have $ m = \log_2 n $. Thus, $ \sqrt[]{n} = 2^{\frac{m}{2}} $.

Then we have: $ T(2^m) = 2 T(2^{\frac{m}{2}}) + \log {2^m} = 2 T(2^{\frac{m}{2}}) + m $. We denote the running time in terms of $ m $ is $ S(m) $, so $ S(m) = T(2^m) $, where $ m = \log n $. so we have $ S(m) = 2S(\frac{m}{2})+ m $.

Now this recurrence can be written in the form of $ T(m) = aT(\frac{m}{b})+ f(m) $, where $ a=2 $, $ b=2 $, and $ f(m)=m $.

$ f(m) = m = \Theta(n^{\log _{b}{a}}) = \Theta(n) $. So the second case of master's theorem applies, we have $ S(k) = \Theta(k^{\log _{b}{a}} \log k) = \Theta(k \log k) $.

Replace back with $ T(2^m) =S(m) $, and $ m = \log_2 n $, we have $ T(n) = \Theta((\log n) (\log \log n)) $.

For the given recurrence, we replace n with $ 2^m $ and denote the running time as $ S(m) $. Thus,we have $ S(m) = T(2^m) = 2 T(2^{\frac{m}{2}}) + m $

(b) $ 3^{f(n)} $ is NOT $ O(3^{g(n)} $). Here is a counter example:

Let $ f(n) = n $ and $ g(n)=\frac{n}{2} $. Then $ f(n) = O(g(n)) $. Now, $ 3^{f(n)}=3^n $, $ f(3^{f(n)})=O(3^n) $; however, $ O(3^{g(n)})=O(3^{\frac{n}{2}}) $. So $ f(3^{f(n)}) \neq O(3^{g(n)}) $.

Solution 2

(a) Assume $ T(n) = O(\log n) $, so
$ \begin{equation} \begin{aligned} T(\sqrt[]{n}) &= O(\log \sqrt[]{n} ) \\ &= O(\frac{1}{2}\log n) \end{aligned} \end{equation} $
So
, $ \begin{equation} \begin{aligned} T(n) &= 2 T(\sqrt[]{n}) + \log n \\ &= O(\log n ) + \log n \\ &= O(\log n) \end{aligned} \end{equation} $

(b) $ f(n) $ is $ O(\log n) $, then

$ f(n) <= g(n) $.

So,

$ \begin{equation} 3^{f(n)} <= 3^{g(n)} \end{equation} $

So, $ 3^{f(n)} $ is $ O(3^{g(n)}) $

Comments on Solution 2:

(a)There is recurrence in the algorithm, $ T(n) = 2 T(\sqrt[]{n}) + \log n $, we can not simply get that $ T(n)= O(\log n ) + \log n $. Change the variable and use the master's theorem will be an appropriate approach.

(b)The second part of the problem is related the answer of first part of the problem.

Back to QE CE question 1, August 2013

Back to ECE Qualifying Exams (QE) page