(6 intermediate revisions by the same user not shown)
Line 20: Line 20:
 
</center>
 
</center>
 
----
 
----
 +
[[ECE-QE_CE1-2013|Back to QE CE question 1, August 2013]]
 +
----
 +
 
'''Problem 1. '''
 
'''Problem 1. '''
  
Line 53: Line 56:
  
 
Let <math>f(n) = n</math> and <math>g(n)=\frac{n}{2}</math>. Then <math>f(n) = O(g(n))</math>.  
 
Let <math>f(n) = n</math> and <math>g(n)=\frac{n}{2}</math>. Then <math>f(n) = O(g(n))</math>.  
Now, <math>3^{f(n)}=3^n</math>, <math>f(3^{f(n)})=O(3^n)</math>; however, <math>O(3^{g(n)})=O(3^{\frac{n}{2}})</math>. So <math>f(3^{f(n)}) \neq O(3^{g(n)})</math>.
+
Now, <math>3^{f(n)}=3^n</math>, <math>f(3^{f(n)})=O(3^n)</math>; however, <math>O(3^{g(n)})=O(3^{\frac{n}{2}})</math>. So <math>f(3^{f(n)}) \neq O(3^{g(n)})</math>.  
  
 
----
 
----
Line 84: Line 87:
  
 
So,
 
So,
 
 
<math>
 
<math>
 
\begin{equation}
 
\begin{equation}
Line 90: Line 92:
 
\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>
  
 
<br>  
 
<br>  
 
 
<font color="red"><u>'''Comments on Solution 2:'''</u>  
 
<font color="red"><u>'''Comments on Solution 2:'''</u>  
  
 
(a)There is recurrence in the algorithm, <math>T(n) = 2 T(\sqrt[]{n}) + \log n </math>, we can not simply get that <math> T(n)= O(\log n ) + \log n </math>. Change the variable and use the master's theorem will be an appropriate approach.
 
(a)There is recurrence in the algorithm, <math>T(n) = 2 T(\sqrt[]{n}) + \log n </math>, we can not simply get that <math> T(n)= O(\log n ) + \log n </math>. 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 <math>O</math>.  <math>f(n) = O(g(n))</math> implied that <math> \limit n-> \infinite </math>  
+
(b)There is some misunderstanding about the definition of the upper limit of <math>O</math>.  <math>f(n) = O(g(n))</math> implied that <math> \lim_{n\to\infty} \frac{f(n)}{g(n)} = 0</math>
 +
In this solution, it claims that <math> f(n) <= g(n) </math>, which is not true.
  
 
<br>  
 
<br>  
 
+
----
  
 
[[ECE-QE_CE1-2013|Back to QE CE question 1, August 2013]]
 
[[ECE-QE_CE1-2013|Back to QE CE question 1, August 2013]]
  
 
[[ECE_PhD_Qualifying_Exams|Back to ECE Qualifying Exams (QE) page]]
 
[[ECE_PhD_Qualifying_Exams|Back to ECE Qualifying Exams (QE) page]]

Latest revision as of 16:06, 23 August 2017


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

Basic linear algebra uncovers and clarifies very important geometry and algebra.

Dr. Paul Garrett