Asymptotic Notation is used to describe the running time of an algorithm. How much time does an algorithm take with a given input of n.
There are three different notations:
- Big O
- Big Theta (Θ)
- Big Omega (Ω)
Calculate the big-Θ of an algorithm by counting the number of iterations the algorithm always takes with an input of n. The runtime can be described as Θ(N).
Calculate the Big-O of an algorithm by counting how many iterations an algorithm will take in the worst-case scenario with an input of N. For example, O(log n) describes the Big-O of a binary search algorithm.
Calculate the big-Ω by counting how many iterations an algorithm will take in the best-case scenario based on an input of N. For example, a Bubble Sort algorithm has a running time of Ω(N).
When an algorithm consists of many parts, we describe its runtime based on the slowest part of the program.
Algorithmic Common Runtimes
Algorithmic runtimes from fastest to slowest:
· constant: Θ(1)
· logarithmic: Θ(log N)
· linear: Θ(N)
· polynomial: Θ(N²)
· exponential: Θ(2^N)
· factorial: Θ(N!)
The speed of an algorithm can be analyzed with a while loop. The loop can be used to count the number of iterations it takes for a function to complete.
Queue Versus Stack
A Queue data structure is based on First In First Out order, like a grocery store line. Therefore, it takes O(N) runtime to retrieve the first value in a Stack because it is all the way at the bottom.
Bubble Sort with Linked List
Bubble Sort is the simplest sorting algorithm for a list. For every element in the list, it compares it with its following neighbor and swaps them if they are in descending order. Each pass of the swap takes O(N). Since there are N elements in the list, it would take N*N swaps. The Big O runtime would be O(N²).