3,009 views
2 votes
2 votes

Running time of an algorithm $T(n),$ where $n$ is input size is given by

$T(n) = \begin{cases} 8 T(n/2) + qn, & \textsf{ if } n>1 \\  p, & \textsf{ if } n=1 \end{cases}$ where $p$ and $q$ are constants. $T(n)$ is 

  1. $\Theta(n^2)$
  2. $\Theta(n^n)$
  3. $\Theta(n^3)$
  4. $\Theta(n)$ 

1 Answer

Best answer
4 votes
4 votes
Case 1 of master theorem as

$f(n) = O\left(n^{\log_b a -\epsilon} \right ) \\= O\left(n^{\log_2 8 -\epsilon }\right) \\= O\left(n^{3 -\epsilon} \right)$

is true for any $ 0 < \epsilon \leq 2$.

Now, the complexity is $\Theta\left(n^{ \log_b a }\right) = \Theta \left(n^3\right)$.
selected by

Related questions

2 votes
2 votes
2 answers
1
pradeepchaudhary asked Jul 14, 2018
9,131 views
Q.6 The time complexity of an algorithm T(n), where n is the input size, is given by— T(n)= T(n-1) + 1/n, if n>1 = 1, otherwise.The order of the algorithm is�...
1 votes
1 votes
1 answer
3
Soumyashree asked Nov 21, 2015
462 views
T(n) = T(n-1)+ 1/n if n>1 =1 otherwiseThe order of the algorithm is
0 votes
0 votes
1 answer
4
syedasafoora asked Nov 8, 2023
221 views
Consider the following algorithm for Build-Max-heap and the given array A=[ 47,96, 35, 54, 77, 65, 83]. Run this algorithm on the given array and redraw the heap and the ...