10.3 How hard can that be, again?

In section 2.8, we first saw and used the O() notation for sorting and searching. Bubble sort runs in O(n²) time, and merge sort is O(n log(n)). A brute force search is O(n), but adding sorting and random access allows a binary search to be O(log(n)).

We now look at complexity again to understand why Shor’s factoring algorithm is a big improvement on known classical methods.

10.3.1 Time is not always on your side

All algorithms are of polynomial time because we can bound them, in this case, by O(n²). More precisely, there is a hierarchy of time complexities. For the examples above, polynomial$time algorithm$polynomial time complexity$polynomial time complexity

Polynomial time is higher than all of these, but we can say each runs in at least polynomial time. exponential$growth growth$exponential

We are concerned with this because there is a special distinction between polynomial...