Line 63: Line 63:
  
 
(b)  
 
(b)  
<math>f(n)</math> is <math>O(\log n)</math>, then <math>f(n) <= g(n)</math>. So,
+
<math>f(n)</math> is <math>O(\log n)</math>, then
 +
 
 +
<math>f(n) <= g(n)</math>.  
 +
 
 +
So,
 +
 
 
<math>
 
<math>
 
\begin{equation}
 
\begin{equation}
Line 69: Line 74:
 
\end{equation}
 
\end{equation}
 
</math>
 
</math>
 +
 +
 
So, <math>3^{f(n)}</math> is <math>O(3^{g(n)})</math>
 
So, <math>3^{f(n)}</math> is <math>O(3^{g(n)})</math>
  

Revision as of 19:16, 20 July 2017


ECE Ph.D. Qualifying Exam

Computer Engineering(CE)

Question 1: Algorithms

August 2013


Solution 1

(a) First, let us change the variable. 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 in 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 an counter example: Let $ f(n) = n $ and $ g(n)=\frac{n}{2} $. Then </math>f(n) = O(g(n))</math>. 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)}) $

Back to QE CE question 1, August 2013

Back to ECE Qualifying Exams (QE) page

Alumni Liaison

Abstract algebra continues the conceptual developments of linear algebra, on an even grander scale.

Dr. Paul Garrett