Hacker News Reader

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

View on HN

In 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.

They’re asking for the tightest upper bound.

There's master theorem though...

Reply on news.ycombinator.com