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(g(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)There is some misunderstanding about the definition of the upper limit of $ O $. $ f(n) = O(g(n)) $ implied that $ \lim_{n\to\infty} \frac{f(n)}{g(n)} = 0 $ In this solution, it claims that $ f(n) <= g(n) $, which is not true.

Back to QE CE question 1, August 2013

Back to ECE Qualifying Exams (QE) page