Big O Notation – Using not-boring math to measure code’s efficiency
interviewcake.com
Big O Notation – Using not-boring math to measure code’s efficiency
1–10 of 100 posts
Re: Big O Notation – Using not-boring math to measure code’s efficiency
#2I have a question for those with a better understanding of such things. Is it difficult to calculate time or memory complexity of a function through static analysis?
It seems kind of basic, but I still find myself manually checking code instead of relying on a tool.
Re: Big O Notation – Using not-boring math to measure code’s efficiency
#3I have a question for those with a better understanding of such things. Is it difficult to calculate time or memory complexity of a function through static analysis? It seems kind of basic, but I still find myself manually checking code instead of relying on a tool.
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
Re: Big O Notation – Using not-boring math to measure code’s efficiency
#4Except Big O Notation is exactly not measuring code's efficiency.
Re: Big O Notation – Using not-boring math to measure code’s efficiency
#5I have a question for those with a better understanding of such things. Is it difficult to calculate time or memory complexity of a function through static analysis? It seems kind of basic, but I still find myself manually checking code instead of relying on a tool.
For a completely arbitrary program, it is not possible to calculate a tight bound on the time or memory complexity of that that program via static analysis. See Rice's Theorem[0].
It is possible to determine interesting properties of programs if you weaken your requirements to approximations and/or add significant constraints. You can maintain properties by construction if you only allow yourself to use certain kinds of building blocks in assembling programs. The less powerful your computational model, the easier it is to prove things about it.
The core idea of a type system is to form a symbolic representation of the semantics of your program which is simpler than the program itself, so that you can prove properties of that simpler system instead of the intractable problem of doing so for the actual program. (If you aren't careful, your type system could end up sufficiently powerful that it is itself undecidable, and you're back where you started.)
Re: Big O Notation – Using not-boring math to measure code’s efficiency
#6I have a question for those with a better understanding of such things. Is it difficult to calculate time or memory complexity of a function through static analysis? It seems kind of basic, but I still find myself manually checking code instead of relying on a tool.
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
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.
Re: Big O Notation – Using not-boring math to measure code’s efficiency
#7 def print_first_item(items):
print items[0]
This function runs in O(1) time (or "constant time") relative to its input.
And if stdout is piped to a process that isn't consuming its input, it might never terminate naturally.
Also, since Python has arbitrarily large integers, an expression like "index += 1" probably runs in O(log(index)) time, not O(1) time.
Re: Big O Notation – Using not-boring math to measure code’s efficiency
#8I have a question for those with a better understanding of such things. Is it difficult to calculate time or memory complexity of a function through static analysis? It seems kind of basic, but I still find myself manually checking code instead of relying on a tool.
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
There's master theorem though...
Re: Big O Notation – Using not-boring math to measure code’s efficiency
#9> not-boring math
What's next? Gradient decent with no gradients? Fourrier transform with no functions?
If math is do boring just skip the whole thing, don't try to kid yourself by saying you're not doing it when you are in fact doing it.
/rant
Re: Big O Notation – Using not-boring math to measure code’s efficiency
#10I have a question for those with a better understanding of such things. Is it difficult to calculate time or memory complexity of a function through static analysis? It seems kind of basic, but I still find myself manually checking code instead of relying on a tool.
The resolution of the Halting Problem shows you can't even determine whether the complexity is finite!