The running time of an algorithm is represented by the following recurrence relation:

$T(n) = \begin{cases} n & n \leq 3 \\ T(\frac{n}{3})+cn & \text{ otherwise } \end{cases}$

Which one of the following represents the time complexity of the algorithm?

Keep practicing — related questions

• What is the order of growth of the running time of an algorithm, if its running time is: T(n) = [n(n log n ...
• The recurrence relation that arises in relation with the complexity of Binary Search is
• The running time of the following algorithm Procedure A(n) If n <= 2 return (1) else return (A($|\sqrt n|$)...
• Let w(n) and A(n) denote respectively, the worst case and average case running time of an algorithm execute...
• Let w(n) and A(n) denote respectively, the worst case and average case running time of an algorithm execute...
• Which of the following asymptotic notations represents the upper bound and the lower bound of the running t...
• What is time complexity of fun()? int fun(int n) { int count = 0; for (int i = 0; i < n; i++) for (int j = ...
• Time complexity of algorithm1 is T (n^2) and that of algorithm2 is T (n).Then which of the following statem...