Is there an online tool that returns the time complexity of recursion functions?
For instance, when I enter $T(n) = T(n/2) + n$, I'd like to get $\Theta(n)$.
I tried using Wolfram Alpha, but it doesn't return the above result I was looking for.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Wolfram Alpha is giving you a more accurate estimate, $T(n) \sim 2n$. However, it can also give you the weaker estimate $T(n) = O(n)$ you are after:
Just click on Show weaker bound.
answered Jan 30, 2021 at 8:57
$\begingroup$
$\endgroup$
You can use my master theorem solver to get tight asymptotic bounds. Using your example:
