The following is a brief summary of the functions demonstrated in the application. You can get more detail here.
Function | Description | Example |
---|---|---|
O(1) | Constant complexity regardless of the domain size. | Array direct indexing, Hash table |
O(n) | Linear complexity. As the domain size increases, the time/complexity increases linearly. If you double the items the complexity will double. | Sequential search |
O(log n) | Logarithmic complexity. As the domain size increases, the time/complexity increases logorithmically | Binary Search on sorted data, Lookup in balanced binary tree |
O(n log n) | Log Linear complexity. As the domain size increases, the time/complexity increases at a log linear or geometric rate. | Heap Sort, Merge Sort, Quick Sort1 |
O(n²) | Quadratic complexity. As the domain size increases, the time/complexity increases quadratically. | Bubble Sort, Insertion sort |
O(n³) | Cubic complexity. As the domain size increases, the time/complexity increases at a cubic rate. | Naive multiplication of two nxn matrices. |
O(2ⁿ) | Exponential complexity. As the domain size increases, the time/complexity increases exponentialy. | Some graph algoritms like finding the exact solution to the traveling salesman problem. |
No comments:
Post a Comment