Some algorithms are more efficient than others at solving a given problem. There are two considerations when analyzing efficiency:
Computer scientists use a mathematical property called complexity as a measure of how efficient algorithms are at solving problems. However, complexity describes algorithmic efficiency as the problem size grows to infinity, and so complexity analysis becomes more relevant in practical applications when dealing with large problems.
When analyzing complexity of an algorithm, we can usually measure the size of the problem that the algorithm solves using a whole number. For instance, if the problem is to sort a sequence of values, then the size of the problem is the number of values to sort. When the size of the problem increases, there is usually an increase in the amount of time and storage space required by the algorithm to solve the problem.
In complexity theory, we characterize the efficiency of an algorithm by providing a simple mathematical function of the problem size that provides an asymptotic bound for the time or space requirements of the algorithm. We say asymptotic, because the function provides a bound as the problem size goes to infinity.
Suppose f(n) represents the average time a particular algorithm runs for problem instances of size n. We say that the average running time of the algorithm is in the order of g(n) if for some positive constant c and positive integer N the following condition holds.
f(n) < c * g(n) when n > N
We define worst-case running time and best-case running time similarly.
We define a function O(g(n)), called big-Oh of g(n), that maps a function g(n) to the set of all functions that are in the order of g(n).
f in O(g) means there exists integer N and positive real number c such that f(n) < c * g(n) when n > N
When the time complexity of an algorithm is in O(n), we say that the algorithm runs in linear time. When the time complexity of an algorithm is in O(1), we say that the algorithm runs in constant time.
As an example, suppose the problem is to determine if a given value appears within a sequence of n values. When the values are unsorted, the standard approach to solve this problem is to compare each element, one after another, with the given value until you either find the element or you have examined all the elements (to conclude that the sequence does not contain it). This algorithm is called linear search. In the worse case, the value doesn't appear in the sequence, so the worst-case running time of linear search will be approximately n times the amount of time needed to perform a single comparison. Therefore, the worst-case running time of linear search in O(n), where n is the number of items in the sequence.
The storage requirements for the execution of the linear search algorithm is fixed, because it does not depend on the number of elements in the sequence. For this reason, the storage complexity of linear search is O(1).
Note that O(a*f(n) + b) = O(f(n)) for all constants a and b. By convention, we always reduce the function in big-Oh notation to its simplest form, so for example we would not use the notation O(2*n). In this course, you are required to express complexity in fully reduced form; if you don't do this on graded activities, you will be marked down for it. Non-linear functions should also be reduced.
If an algorithm has no loop, or if the number of times a loop runs is bounded by some fixed value for all possible instances on which the algorithm runs, then the algorithm runs in constant time. In other words, the time complexity is O(1).
Suppose an algorithm takes instances of size n. If the algorithm contains a single loop whose number of iterations equal a constant multiple of n, then it runs in linear time (O(n)).
Suppose we want to sort a sequence of n values using bubble sort. In the outer loop, the counter i runs from n - 1 to 0. For pass i of the outer loop, the inner loop runs i times. Thus, the total number of repetitions is:
(n - 1) + (n - 2) + ... + 1
But this is less than n + (n - 1) + ... + 1, which equals n * (n + 1) / 2. Thus, the running time of Bubble Sort is O(n^2).
Suppose we use the insertion sort to re-organize a sequence of items into ascending order. Consider the case when the sequence starts in descending order. In this case, the inner loop runs the maximum number of times for each iteration of the outer loop. An analysis similar to the bubble sort demonstrates that the running time of insertion sort in this worst case is O(n^2).
Now, consider the case when the sequence of n items is already in ascending order. In this case, execution never enters the inner loop, thus the running time will be bounded by some multiple of n. Thus, the best case running time of insertion sort is O(n).
Note: if all instances of size n are equally likely, then the average running time of insertion sort is O(n^2).
The worst case running time of binary search is log(n). The reason for this is that each time the binary search loop executes, it divides the number of items that it's concerned with by 2. The number of times a number n can be divided by 2 is approximately log(n).
When an algorithm can be separated into a sequence of sub-algorithms, the running time of the overall algorithm will be the running time of the sub-algorithm with the greatest running time.
Determination of Storage Complexity
For the purposes of this class, storage complexity is determined by considering the maximum amount of memory needed by an algorithm minus the maximum amount of memory needed to satisfy its pre- and post-conditions. For example, suppose you have a problem that requires 4(n-1) bytes of memory to store the data coming into the algorithm and 4n bytes to store data needed after the algorithm completes. If maximum amount of memory the algorithm uses at any point in time is 4n + 100, then the storage complexity of the algorithm should be based on 100, and thus is in O(1).