ECE Ph.D. Qualifying Exam

Computer Engineering(CE)

Question 1: Algorithms

August 2013


Back to QE CE question 1, August 2013


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

Alumni Liaison

Prof. Math. Ohio State and Associate Dean
Outstanding Alumnus Purdue Math 2008

Jeff McNeal