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

R**untime** 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 *x*0 (e.g., *x*0 = 5) such that *f*(*x*) ≤ *cg*(*x*) whenever *x* ≥ *x*0.

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!)*

A**nalysing 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,

**; so its running time complexity will be equal to**

*grade*variable will be assigned equal to ‘*A*’**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

**‘**and, lastly,

*if the score is 80 or above*’ statement**; so its running time complexity will be equal to**

*grade*variable will be assigned equal to ‘B’**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

**‘**and the

*if the score is 70 or above*’ statement**; on the other hand, if the student get lower than 60,**

*grade*variable will be assigned equal to ‘C’**.**

*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