| (26 intermediate revisions by the same user not shown) | |||
| Line 19: | Line 19: | ||
August 2013 | August 2013 | ||
</center> | </center> | ||
| + | ---- | ||
| + | [[ECE-QE_CE1-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: <br> | ||
| + | <math> | ||
| + | \begin{equation} | ||
| + | T(n) = 2T(\sqrt[]{n}) + \log n | ||
| + | \end{equation} | ||
| + | </math> | ||
| + | Find the asymptotic run time complexity of this algorithm. Give details of your computation. | ||
| + | |||
| + | (b) Assume functions <math>f</math> and <math>g</math> such that <math>f(n)</math> is <math>O(g(n))</math>. Prove or disprove that <math>3^{f(n)}</math> is <math>O(3^{g(n)})</math>. | ||
| + | ---- | ||
| + | ===Share and discuss your solution below. === | ||
---- | ---- | ||
===Solution 1=== | ===Solution 1=== | ||
| − | First, let us change the | + | (a) First, let us change the variables. Let <math>n = 2^{m}</math>, so equivalently, we have <math>m = \log_2 n</math>. Thus, <math>\sqrt[]{n} = 2^{\frac{m}{2}}</math>. |
Then we have: | Then we have: | ||
<math>T(2^m) = 2 T(2^{\frac{m}{2}}) + \log {2^m} = 2 T(2^{\frac{m}{2}}) + m</math>. | <math>T(2^m) = 2 T(2^{\frac{m}{2}}) + \log {2^m} = 2 T(2^{\frac{m}{2}}) + m</math>. | ||
| − | |||
We denote the running time in terms of <math>m</math> is <math>S(m)</math>, so <math>S(m) = T(2^m)</math>, where <math>m = \log n</math>. | We denote the running time in terms of <math>m</math> is <math>S(m)</math>, so <math>S(m) = T(2^m)</math>, where <math>m = \log n</math>. | ||
so we have <math>S(m) = 2S(\frac{m}{2})+ m</math>. | so we have <math>S(m) = 2S(\frac{m}{2})+ m</math>. | ||
| − | Now this recurrence can | + | Now this recurrence can be written in the form of <math>T(m) = aT(\frac{m}{b})+ f(m)</math>, where <math>a=2</math>, <math>b=2</math>, and <math>f(m)=m</math>. |
<math>f(m) = m = \Theta(n^{\log _{b}{a}}) = \Theta(n)</math>. So the second case of master's theorem applies, we have <math>S(k) = \Theta(k^{\log _{b}{a}} \log k) = \Theta(k \log k)</math>. | <math>f(m) = m = \Theta(n^{\log _{b}{a}}) = \Theta(n)</math>. So the second case of master's theorem applies, we have <math>S(k) = \Theta(k^{\log _{b}{a}} \log k) = \Theta(k \log k)</math>. | ||
| Line 36: | Line 52: | ||
For the given recurrence, we replace n with <math>2^m</math> and denote the running time as <math>S(m)</math>. Thus,we have <math>S(m) = T(2^m) = 2 T(2^{\frac{m}{2}}) + m</math> | For the given recurrence, we replace n with <math>2^m</math> and denote the running time as <math>S(m)</math>. Thus,we have <math>S(m) = T(2^m) = 2 T(2^{\frac{m}{2}}) + m</math> | ||
| + | |||
| + | (b) <math>3^{f(n)}</math> is NOT <math>O(3^{g(n)}</math>). Here is a counter example: | ||
| + | |||
| + | 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>. | ||
| + | |||
| + | ---- | ||
| + | ===Solution 2=== | ||
| + | (a) Assume <math>T(n) = O(\log n)</math>, so <br> | ||
| + | <math> | ||
| + | \begin{equation} | ||
| + | \begin{aligned} | ||
| + | T(\sqrt[]{n}) &= O(\log \sqrt[]{n} ) \\ | ||
| + | &= O(\frac{1}{2}\log n) | ||
| + | \end{aligned} | ||
| + | \end{equation} | ||
| + | </math> | ||
| + | <br> | ||
| + | So<br>, | ||
| + | <math> | ||
| + | \begin{equation} | ||
| + | \begin{aligned} | ||
| + | T(n) &= 2 T(\sqrt[]{n}) + \log n \\ | ||
| + | &= O(\log n ) + \log n \\ | ||
| + | &= O(\log n) | ||
| + | \end{aligned} | ||
| + | \end{equation} | ||
| + | </math> | ||
| + | |||
| + | (b) | ||
| + | <math>f(n)</math> is <math>O(g(n))</math>, then | ||
| + | |||
| + | <math>f(n) <= g(n)</math>. | ||
| + | |||
| + | So, | ||
| + | <math> | ||
| + | \begin{equation} | ||
| + | 3^{f(n)} <= 3^{g(n)} | ||
| + | \end{equation} | ||
| + | </math> | ||
| + | |||
| + | So, <math>3^{f(n)}</math> is <math>O(3^{g(n)})</math> | ||
| + | |||
| + | <br> | ||
| + | <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. | ||
| + | |||
| + | (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> | ||
| + | ---- | ||
[[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
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)}) $.
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.
