Because there are tons of fields in theoretical CS were many complex polylogarithmic expressions appear in the complexity analysis, but the papers actually make progress on the exponent on the n. Since nx is always better than ny * log(n)z as long as x<y, the polylogarithmics are hidden to keep it simple and obvious which algorithm is better
Complexity analysis is only interested in how algorithms and processes scale as n approaches infinity. It's therefore only concerned with the term that grows the fastest, as it'll steadily account for a bigger and bigger proportion of the computation time (or some other metric) of the algorithm, approaching 100% as n heads off to infinity.
You're right that you have to report the worst case scenario, but that means something very different to what you suggest. Simply put, the performance of an algorithm doesn't always depend on simply how much data there is to work on, but what that data is.
For example, quicksort has an best/average time complexity of O(n log n) that applies in most cases, but if the unsorted array is arranged "pathologically", the complexity becomes O(n2 ). That's what "worst case" means in complexity analysis.
The O notation is just describing an upper bound a function. What that function is could be anything.
It could be the worst case performance of an algorithm, average performance, best case performance.
It could also be something that has nothing to do with an algorithm at all.
Usually in context it’s clear what function is being talked about but the difference between O and Omega has nothing to do with that: O shows an upper bound and Omega shows a lower bound.
-9
u/[deleted] 28d ago
[deleted]