Register

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

176 views

1 Answer

0 0 votes

$T(n)=10T(n/3)+17n^{1.2}$

Using the Master Theorem:

$a=10$, $b=3$, and $f(n)=17n^{1.2}$

Calculate:

$n^{\log_b a}=n^{\log_3 10}$

Since $\log_3 10\approx 2.096$, $n^{1.2}$ grows slower than $n^{\log_3 10}$.

Therefore, this is Master Theorem Case $1$.

$T(n)=\Theta(n^{\log_3 10})$

Answer: B. $O(n^{\log_3 10})$

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

2 2 votes
1 1 answer
277
277 views
GO Classes asked Jul 29
277 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)$
3 3 votes
1 1 answer
194
194 views
GO Classes asked Jul 29
194 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)$
2 2 votes
1 1 answer
182
182 views
GO Classes asked Jul 29
182 views
GO Classes DPP | GATE CS, DA | Algorithms | Master's Theorem
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)$
1 1 vote
1 1 answer
212
212 views
GO Classes asked Aug 31
212 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 ...