Analysis of algorithms

To analyze an algorithm is to determine the quantity of resources (such as time and storage) which will be necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length. Usually the efficiency of an algorithm is stated as a function of input length. Big O notation, omega notation and theta? notation are used to specify this. For instance, binary search is said to run in logarithmic time, or in O(log(n)); more precisely, if the sorted set in which we search has n elements, log₂ N + 1 steps are needed to return an answer.

Complexity theory provides minimum bounds on the resources needed by any algorithm which solves a given computational problem. When the complexity of a problem is known, it is hopeless to search for ways to solve it more efficiently than what this function specifies.

/Talk