eli5: What does Big Oh, Big Omega, and Big Theta mean in algorithm?
In: 0
Big theta notation (and the others) describe how the runtime of an algorithm scales as the input size increases. A theta(1) algorithm takes the same amount of time no matter how many elements there are. Getting a value from an array is the same whether it is the 3rd or 300th element. A theta(n) algorithm’s runtime scales the same as the input. If you are finding the maximum value in an array, you have to check each number to find it, so it scales with the input. More complicated algorithms can have higher and higher big theta. A selection sort (not the best sorting algorithm but a good example) will go through each number in an list, find the lowest, then add it to a new list, repeating until the new list contains each element in order. This requires going through a list of n items n times so it is theta(n^2). When you double the size of the input, it will take about 4x as long to complete. Similarly when you have a theta(n^3) algorithm, doubling the input will multiply the runtime by 8.
There is a more precise mathematical definition of big theta notation, but this understanding is good enough for now. Big O(n) is basically an upper bound on how the runtime grows, and big omega is basically a lower bound on how the runtime grows. An O(n) algorithm is known to take theta(n) time or less, an Omega(n) algorithm is proven to take theta(n) time or more. If a problem is both O(n) and Omega(n), then it is also theta(n).
Latest Answers