Analysis of Algorithms

The naive way to compare the performanace of 2 algorithms is to run both of them by given the same input and measure time or space that they use. This is quite not effective some algorithms might good at small dataset but get worse at large or vise versa. To measure performance of algorithms, we use Asymptotic analysis to do. It’s mathematical analysis on algorithms f(n) as n(number of input) -> ∞. Which we also usually expressed as Big O notation.

All Bigs

• Big O Also calls upper bound, the worst case.
• Big Omega Ω Also calls lower bound, the best case.
• Big Theta Θ

Some algorithms have difference performanace given same input size but difference input data. For example, find String in sorted string list. Let’s say the algorithm is simple brute force looping. The lower bound(best case) is that the answer is at the first of the list, so Big Omega is Ω(1). In contrast, if the answer is at the last of the list, then this is consider the worst case because we have to check one by one until the end, so Big O is O(n).