Part 2: Algorithm Analysis
Running code efficiently requires many components: simple, correctness, and short runtime. We cannot disagree that runtime will create the difference from other same functional programs.
Runtime of a program depends on number of steps the program executes and input size. The more number of execution steps, the longer it takes to finish.
Analysis Runtime:
One of the most important KEYWORD in this chapter is Big-O which describes what is called an asymptotic upper bound.
Example of Big O notation: f(x) ∈ O(g(x)) as there exists c > 0 (e.g., c = 1) and x0 (e.g., x0 = 5) such that f(x) ≤ cg(x) whenever x ≥ x0.
In the fact that, we can say that Big-O is used to describe the worst-case of running time of the algorithm.
In the other hand, the fastest possible running time (which is best-case in algorithm) for any algorithm is O(1) which is Constant Running Time
Running Time Complexity (from best to worst):
constant O(k) < logarithmic O(log(n)) < linear O(n) < superlinear O(n*log(n)) < polynomial O(n^c) < exponential O(c^n) < factorial O(n!)
Analysing running time from pseudocode/actual code: we should be able to analyse the worst-case running time (also best-case) in our system. Here is a simple example,
If the student has score higher than 90, the execution of the code will go to the first condition which is ‘if the score is 90 or above’ statement and, grade variable will be assigned equal to ‘A’; so its running time complexity will be equal to 2 (for checking condition and assigning variable).
Else if the student has score higher than 80 but lower than 90, the execution of the code will go to ‘else’ statement (which below ‘if the score is 90 or above’ statement). Then code will execute ‘if the score is 80 or above’ statement and, lastly, grade variable will be assigned equal to ‘B’; so its running time complexity will be equal to 3 (for checking 2 conditions and assigning variable).
Or, else if the student has score lower than 80, the execution of the code will go to ‘else’ statement for 2 times. If the student get higher than 70, then code will execute ‘if the score is 70 or above’ statement and the grade variable will be assigned equal to ‘C’; on the other hand, if the student get lower than 60, grade variable will be assigned equal to ‘F’. So its running time complexity will be equal to 4 (for checking 3 conditions and assigning variable).
As the result, we see that the student who get higher than 90 will be the best-case (lowest running-time) and who get lower than 70 will be the worst-case (highest running-time).
From previous example, it is a very simple analysing running time. There are more complex questions to analyse the code (which contains loop, dependent-variable, independent-variable, etc.); being professional, we need to practice a lot of questions.
Reference:
PCA Lab, Computer Innovation Engineering, KMITL https://www.geeksforgeeks.org/analysis-algorithms-big-o-analysis/ https://en.wikipedia.org/wiki/Big_O_notation#/media/File:Big-O-notation.png
