-
Book Overview & Buying
-
Table Of Contents
-
Feedback & Rating

Dancing with Qubits
By :

In section 2.8, we first saw and used the O() notation for sorting and searching. Bubble sort runs in O(n2) 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.
All algorithms are of polynomial time because we can bound them, in this case, by O(n2). 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...