I\'m used to search for the Landau (Big O, Theta...) notation of my algorithms b
ID: 646304 • Letter: I
Question
I'm used to search for the Landau (Big O, Theta...) notation of my algorithms by hand to make sure they are as optimized as they can be, but when the functions are getting really big and complex, it's taking way too much time to do it by hand. it's also prone to human errors.
I spent some time on Codility (coding/algo exercises), and noticed they will give you the Landau notation for your submitted solution (both in Time and Memory usage).
I was wondering how they do that... How would you do it?
Is there another way besides Lexical Analysis or parsing of the code?
This question concerns mainly PHP and or JavaScript, but I'm opened to any language and theory.
Explanation / Answer
I was wondering how they do that... How would you do it?
I imagine that they are actually estimating the Big O measures ... by running the program for different problem sizes, measuring time and space usage, and fitting curves to the results.
The problem with this approach is that it can get it wrong if the cost functions change shape as N gets large; e.g. 1000 N + N^1.5.
Is there another way besides Lexical Analysis or parsing of the code?
Lexical analysis and parsing are not sufficient. You also need to do some reasoning about the behaviour of the algorithm. And doing that automatically for a previously unknown algorithm is hard.