SLOG-WEEK Ten

Prof Heap covered some concepts about analyzing algorithm in this week's lecture. In computer science  algorithm analysis is a field which deals with the efficiency of algorithms. Efficiency is determined by an algorithm's time complexity and memory usage instead of computer hardware(CPUs, GPUs etc). An algorithm's time complexity is determined by the input size and number of steps the function takes to complete its task. A notation to represent time complexity is the symbol of Big-Oh. For example, a linear algorithm has time complexity of O(n) because if the input size increases, the number of steps it takes to complete also increases, and vice versa. Furthermore, an algorithm has a time complexity of O(n^2) is when number of steps increases quadratically as the input increases.

 

Below is some time complexity classes in descending efficiency order.

O(1), O(log(n)), O(n), O(nlog(n)), O(n^2), O(2^n),O(n!)

There exist some algorithms that have same time complexity(O(1)) for every input, an example for that is the pop method (list) in python. However, most algorithms will be more efficient for some particular input while others will be less efficient. The time complexity also has three categories which are the best case, average case and worst case. Best case is when the algorithm is at its best performance, average case is when the algorithm is at its averages performance, and worst case is when the algorithm is at its worst case complexity. With theses three cases, we can perform analysis of the time complexities of algorithms.