| Line 28: | Line 28: | ||
\end{equation} | \end{equation} | ||
</math> | </math> | ||
| + | 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)})$. | ||
Revision as of 17:24, 20 July 2017
Computer Engineering (CE)
Question 1: Algorithms
August 2013
Question
Part 1. 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.
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)})$.
