| Line 30: | 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. | ||
| − | (b) Assume functions <math> | + | (b) Assume functions <math>f</math> and <math>f</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 17:27, 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 $ f $ such that $ f(n) $ is $ O(g(n)) $. Prove or disprove that $ 3^{f(n)} $ is $ O(3^{g(n)}) $.
