So after reading a lot of information around asymptotic analysis of algorithms and the use of Big O / Big Ω and Θ, I’m trying to grasp how to utilise this in the best way when representing algorithms and operations on data structures.
For example there is a recommended website where I got this screenshot from describing Quicksort and I’ve noticed a few issues that stand out to me based on what I’ve learnt.
- Is it possible for all notations to represent “Best” “Average” and “Worst” cases? and if so how is this possible? For example for a “Worst” case, How can Big Ω represent the Upper bound. The upper bound is tied to Big O.
- I thought in order to find Theta Θ, Big O and Big Ω had to be the same values? In the screenshot “Best” case is
n log(n)and Worst case is
n^2so how can
- Take for instance a Hash Table data structure, if you were to perform an analysis on the time complexity for insertion of an element. Would I be correct is saying you could interchangeably say
O(N)or conversely “Average Case is O(1)” and “Worst Case is O(N)”?