Timeline for Time complexity of functions that call each other
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 20, 2017 at 8:23 | comment | added | gnasher729 | The result can easily be calculated in O(n) if you replace foo (x-1)+f(x-1) with 2*f(x-1). | |
| Jan 20, 2017 at 8:19 | comment | added | gnasher729 | The functions return a value - that's the result. You can do the calculation faster. That doesn't change the result. Usually the result is important. | |
| Jan 19, 2017 at 12:11 | comment | added | David Richerby | Note that $\geq\Theta(f)$ is just $\Omega(f)$. | |
| Jan 19, 2017 at 7:33 | comment | added | Mike Sweeney |
I think I understand the first part but what if I wanted to get a tighter bound and account for the call to bar(x/2)? Also, I'm not clear what your last sentence regarding the result is and where the linear part is coming into the picture.
|
|
| Jan 18, 2017 at 21:52 | history | answered | gnasher729 | CC BY-SA 3.0 |