Complexity Theory Basics
Bounded by above and below, theta notation:
Examples:
Examples:
Linearithmic time complexity is the threshold
Let’s use quick sort as an example, where a pivot is picked in an array, and everything smaller goes “to the left” of the pivot and everything larger goes “to the right” of the pivot. The “left” and “right” sides are then passed on to quicksort() for recursion. When thinking about an algorithm’s time complexity, we consider three cases. Best case: if the array is already sorted, quicksort (depending on how it’s implemented) will take O(N) time. Worst case: if the largest item in the array is picked as the pivot, then N-1 items are passed to the recursive function. This takes O(N*N) time. Expected casBese: We expect the pivot to not be the best or worst case on average, and expect a run time of O(N log N).
Best, worst, and expected cases have nothing to do with O, Omega, and Theta notation. The former describe the big O for different inputs. Big O, Omega and Theta describe the upper, lower, and tight bounds for a runtime.
Space Complexity
Space complexity mirrors time complexity in notation. If an array of size n is used, space complexity is O(n), if it is a two dimensional array of size n by n, the space complexity is O(n*n).
Stack space in recursion also counts, the following runs in O(N) time and takes up O(N) space:
Recursion uses the execution stack to store its memory, this stack acts like a “normal” stack in that it is LIFO. We will see the use of the execution stack as an underlying data structure in many algorithms.
We drop constants and non dominant terms, for example O(2N*N + 400N) just becomes O(N*N).
Adding or Multiplying Multi Part Algorithms
The following is O(A + B):
The following is O(A*B):
Complexity Classes
P = Polynomial
NP = Non deterministic polynomial
O(N^k) where k > 0 are considered problems of P complexity class.
Research NP problems. Start with integer factorization.
Analyzing Loops
Case Studies
Linear Search
Worst case: when the item we are searching for is not in the array:
Binary Search
First take the middle index, and compare with 22. If larger, then we can eliminate everything to the right of the middle index
Next we take the middle of the left hand side and say it’s 23 (index 3), we can compare it to 22, see that it is larger, and eliminate everything to the right of that
Next we take the “middle” of the remaining items and check it against 22, and see that they are equal and return index 2
This takes 3 steps instead of a possible N steps.
Bubble Sort
Testing it with random inputs:
