Recent questions tagged master-theorem

Solve the recurrence:$T(n) = 4T(n/2) + n^2$$\Theta(n^2)$ $\Theta(n^2\log n)$ $\Theta(n^{\log_2 4})$ $\Theta(n^3)$

Solve the recurrence:$T(n) = 7T(n/2) + n^3$$\Theta(n^{\log_2 7})$ $\Theta(n^3)$ $\Theta(n^3\log n)$ $\Theta(n^2)$

Solve the recurrence:$T(n) = 10T(n/3) + 17n^{1.2}$ $O(n^{1.2})$ $O(n^{\log_3 10})$ $O(n^{1.2}\log n)$ $O(n^3)$

Solve the recurrence:$T(n) = 3T(n/5) + (\log n)^2$ $O((\log n)^2)$ $O(n^{\log_5 3})$ $O(n)$ $O(n\log n)$

Consider the following:For all $n>1$$$\begin{aligned}& T_1(n)=4 T_1(n / 2)+T_2(n) \\\\& T_2(n)=5 T_2(n / 4)+\theta\left(\log _2 n\right)\end{aligned}$$Assume that for all...

Consider the following recurrence relation describing the running time of an algorithm: $$T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log n}$$$$(Base\ condition: T(1) =...

How to check if f(n) is polynomially greater than g(n)?

$T\left ( n \right )= 8T\left ( \frac{n}{2} \right )+\left ( n\cdot logn \right )^{2.99}$Also can $\mathcal{O}(n^{3})$ be an upper bound to above recurrence relation?

how do i apply master theorem to this?

how do i apply master theorem to this? T(n)=2T(n/2)−n^3n

how do i apply master theorem to this? 𝑇(𝑛)=16𝑇(𝑛/4)+5𝑛^3

In the recurrence relation$\text{T}(n)=0.5\ast \text{T}(n/2)+1/n$, which case of Master Theorem is suitable?Case $1$Master Theorem not applicable in this situationCase $2...

I can't figure out how to proceed and which case it's falling under after calculating h(n)

which formula to use in master theorm

The running time of an algorithm $T(n),$ where $’n’$ is the input size , is given by$T(n) = 8T(n/2) + qn,$ if $n>1$ $= p,$ if $n = 1$Where $p,q$ are constants. ...

The running time of an algorithm $T(n),$ where $’n’$ is the input size , is given by$T(n) = 8T(n/2) + qn,$ if $n>1$$ = p,$ if $n = 1$Where $p,q$ are constants. The order ...

The master theoremassumes the subproblems are unequal sizescan be used if the subproblems are of equal sizecannot be used for divide and conquer algorithmscannot be used ...

Can the master method be applied to the recurrence $T(n)=4T(n/2)+n^2\ lg\ n$ ?Why or why not? Give an asymptotic upper bound for this recurrence.

Use the master method to show that the solution to the binary-search recurrence $T(n)=T(n/2) + \Theta(1)$ is $T(n)=\Theta(lg\ n)$.

Professor Caesar wishes to develop a matrix-multiplication algorithm that is asymptotically faster than Strassen’s algorithm. His algorithm will use the divide and conque...

Use the master method to give tight asymptotic bounds for the following recurrences.$T(n)=2T(n/4) + 1$$T(n)=2T(n/4) +\sqrt{n}$$T(n)=2T(n/4) +n$$T(n)=2T(n/4) +n^2$