4 ms·
I would argue it isn't tractable. f(n) = f(n-1) + f(n-1) has runtime O(2^n); f(n) = f(n-1) + f(n-2) has runtmie O(~1.62^n); f(n) = f(n/2) + f(n/2) has O(n log
by zuza 7y ago
I would argue it isn't tractable.
f(n) = f(n-1) + f(n-1) has runtime O(2^n);
f(n) = f(n-1) + f(n-2) has runtmie O(~1.62^n);
f(n) = f(n/2) + f(n/2) has O(n log n);
for i = 1 to f(n) has runtime f(n).. good luck determining a function output through static analysis
- gizmo686 7y agoIn both cases it has O(2^n). Normally speaking, this response would be pure pedantry [0], but for static analysis it might be good enough. In most cases, the naive answer will be good enough, and the tool can direct you to pay attention to areas of particular concern. Getting static guarantees about performance would require carefully constructing your code with the tool in mind. [0] Although I still find it outrageous that CS departments describe their algorithms class as "math" when they do not accept this answer.
- SamReidHughes 7y agoThey’re asking for the tightest upper bound.
- enedil 7y agoThere's master theorem though...