New answers tagged

0 votes

How to Solve the Recurrence Relation $T(n) = 8T\left(\frac{n - \sqrt{n}}{4}\right) + n^2$ in terms of $\Theta$?

$(n - \sqrt n) / 4$ is slightly smaller than n/4, for example >= $n \cdot (3/16)$ if n >= 16. So you get a lower limit if you take $8T(n \cdot (3/16)) + n^2$ If n >= 64, then $n - \sqrt n >...
gnasher729's user avatar
  • 29.4k
2 votes

How to solve the recurrence $ T(n) = 4T\left(\frac{n}{2}\right) + \frac{n}{\lg n} $ in terms of $\Theta$?

If you want to see it explicitly here is the calculation: $T(n)=4T\left(\frac{n}{2}\right) + \frac{n}{\log n}$ implies that the total number of recursions we do is $\log_2 n$. At the pass of the ...
SilvioM's user avatar
  • 828
1 vote

How to Solve the Recurrence Relation $T(n) = 8T\left(\frac{n - \sqrt{n}}{4}\right) + n^2$ in terms of $\Theta$?

It’s asymptotically the same as the simple recurrence $$T'(n)=8T'(n/4)+n^2,$$ which solves to $T'(n)\sim2n^2$ by any of the common methods (where as usual, I write $f(n)\sim g(n)$ for $\lim_{n\to\...
Emil Jeřábek's user avatar
1 vote
Accepted

what is the complexity of this sorting algorithm?

Let $M(n)$ be the runtime of mergeLevel on an input of size $n$, and let $Q$ be the runtime of quickLevel on an input of size $n$. By inspecting the code, we see that $M(n) = 2Q(\frac{n}{2}) + n$ and $...
Arno's user avatar
  • 2,995
1 vote

Can you short-cut the substitution method for recurrence solving? (Wrong Guess but End Result Works)

No, you can't. As an example, consider the recurrence $T(n) = 4T\left(\frac{n}2\right) + n^2$. If you assume $T(n) \leqslant cn^2 - dn$, using substitution method, you will get to: $$T(n) \leqslant 4\...
Nathaniel's user avatar
  • 13.9k
1 vote

Solving recurrence by iteration, choosing base case

If you have a recurrence that doesn’t apply to the case n = 1, then it would be correct to assume T(1) = c, for some unknown c, and resolve the recurrence based on that; this would be useful if you ...
gnasher729's user avatar
  • 29.4k

Top 50 recent answers are included