Analysis of algorithms
this wiki
Algorithm analysis is an important part of a broader computational complexity theory, which provides theoretical estimates for the resources needed by any algorithm which solves a given computational problem. These estimates provide an insight into reasonable directions of search of efficient algorithms.
Big O notationEdit
Big O notation is used to detemine the orders of growth of an algorithm, especially those with iterations or recursions. Generally, big O notation is used in asymptotic analysis of mathematical functions. In computer science, it is used to provide a measure for the best of an algorithm.
The best case is when an algorithm completes with the least operations done. For example, a linear search algorithm is in best case when the item is at the beginning of the list. The worst case is when an algorithm completes with the most possible operations done. For example, a linear search algorithm is in worst case when the item is at the end of the list. The average case is the expected case for any arbitrary input. These cases need not necessarily be not equal.
Frequent big O notations (examples using average-case time complexity) are:
Notation | Name | Example |
---|---|---|
O(1) | constant | Looking up an item in a random access list, adding an item to a linked list |
O(log n) | logarithmic | Looking up an item in a sorted list using binary search |
O(n) | linear | Looking up an item in a linked list |
O(n log n) = O(log n!) | linearithmic | Performing heapsort or merge sort |
O(n^{2}) | quadratic | Performing bubble sort or insertion sort |
O(n^{3}) | cubic | Multiplying two nxn matrices |
O(c^{n}), c > 1 | exponential | Determining if two logical statements are equal using brute force |
O(n!) | factorial/combinatorial | Solving a traveling salesman problem using brute force |