Computer Engineering(CE)

Question 1: Algorithms

August 2013

Problem 1.

(a) Assume the run time for some algorithm is given by the following recurrence:
$$$T(n) = 2T(\sqrt[]{n}) + \log n$$$ 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{aligned} T(\sqrt[]{n}) &= O(\log \sqrt[]{n} ) \\ &= O(\frac{1}{2}\log n) \end{aligned}
So
, \begin{aligned} T(n) &= 2 T(\sqrt[]{n}) + \log n \\ &= O(\log n ) + \log n \\ &= O(\log n) \end{aligned}

(b) $f(n)$ is $O(g(n))$, then

$f(n) <= g(n)$.

So, $$$3^{f(n)} <= 3^{g(n)}$$$

So, $3^{f(n)}$ is $O(3^{g(n)})$

(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.