| Line 22: | Line 22: | ||
==Question== | ==Question== | ||
'''Part 1. ''' | '''Part 1. ''' | ||
| − | + | (a) Assume the run time for some algorithm is given by the following recurrence: | |
| − | Assume the run time for some algorithm is given by the following recurrence: | + | |
<math> | <math> | ||
\begin{equation} | \begin{equation} | ||
| Line 31: | Line 30: | ||
Find the asymptotic run time complexity of this algorithm. Give detail of your computation. | Find the asymptotic run time complexity of this algorithm. Give detail of your computation. | ||
| − | 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)})$. | + | (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>. |
Revision as of 16:26, 20 July 2017
Computer Engineering (CE)
Question 1: Algorithms
August 2013
Question
Part 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 detail of your computation.
(b) Assume functions $ $f$ $ and $ $g$ $ such that $ $f(n)$<.math> is <math>$O(g(n))$ $. Prove or disprove that $ $3^{f(n)}$ $ is $ $O(3^{g(n)})$ $.
