Register

GO Classes DPP | GATE CS, DA | Algorithms | Master's Theorem

• retagged by
216 views

1 Answer

0 0 votes

Given:

$T(n)=3T(n/5)+(\log n)^2$

Using the Master Theorem:

$a=3$, $b=5$, and $f(n)=(\log n)^2$

Calculate:

$n^{\log_b a}=n^{\log_5 3}$

Since $(\log n)^2$ grows slower than $n^{\log_5 3}$, this is Master Theorem Case $1$.

Therefore:

$T(n)=\Theta(n^{\log_5 3})$


Answer: B $O(n^{\log_5 3})$

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

3 3 votes
1 1 answer
311
311 views
GO Classes asked Jul 29
311 views
GO Classes DPP | GATE CS, DA | Algorithms | Master's 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)$
4 4 votes
1 1 answer
224
224 views
GO Classes asked Jul 29
224 views
GO Classes DPP | GATE CS, DA | Algorithms | Master's Theorem
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)$
3 3 votes
1 1 answer
214
214 views
GO Classes asked Jul 29
214 views
GO Classes DPP | GATE CS, DA | Algorithms | Master's Theorem
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)$
3 3 votes
1 1 answer
306
306 views
GO Classes asked Aug 31
306 views
GO Classes DPP | GATE CS, DA | Algorithms | Directed Graph
Let $G$ be a directed graph with nonnegative edge weights, and let $s$ and $t$ be vertices of $G$.Consider the statement:Any shortest path from $s$ to $t$ in $G$ is also ...