5 Analysis of Algorithms
T.V. Geetha
Welcome to the e-PG Pathshala Lecture Series on Data Structures. This time we are going to talk about the basics of analysis of algorithms. This is important because algorithms use data structures for their implementation.
Learning Objectives
The learning objectives of this module are as follows:
• To understand the concepts of algorithms
• To appreciate the need for the analysis of algorithms
• To know about the analysis of algorithms using Big Oh notation
• To understand analysis using recurrence equations
5.1 Introduction
First let us understand the definition of an Algorithm. Algorithm is defined as “a clearly specified set of simple instructions to be followed to solve a problem”. An algorithm takes a set of values, as input and produces a value, or set of values, as output – in essence it is a mapping of input to output. The important aspect here is that the instructions or steps to be followed for solving the problem should be clearly specified taking care to consider all possible inputs including inputs that could signal errors.
5.2 Properties of Algorithms
In addition to the basic definition of an algorithm given above, the algorithm is associated with certain properties as given below:
• An algorithm must always be correct, in other words the algorithm should always computes the proper function.
• An algorithm must be composed of a series of concrete steps and these steps should be defined in such a way that they are executable by the machine considered.
• An algorithm should be so designed that there can be no ambiguity as to which step will be performed next.
• An algorithm should be composed of only a finite number of steps that is executable in finite time.
• In other word, an algorithm must terminate.
We frequently interchange the use of the terms “algorithm” and “program” though they are actually different concepts. An algorithm outlines the logical sequence of concrete steps to solve a problem whereas the steps outlined by the algorithm are mapped using the syntax of the programming language concerned to produce a program.
5.3 Introduction to Analysis of Algorithms
Algorithm analysis is a process of determining the resources required when executing an algorithm. The resources considered include memory, communication bandwidth and computational time, The last resource is usually considered the most important. The running time of an algorithm is almost always independent of the programming language.
Now let us understand the purpose of analyzing an algorithm. Basically the algorithm is analysed to estimate how long a program will run by analyzing an algorithm’s running time without coding it. Analyzing an algorithm will also help to estimate the largest input that can reasonably be given to the program. It also helps to compare the efficiency of different algorithms and to focus on the parts of code that are executed the largest number of times. Finally the analysis of an algorithm helps to choose an appropriate algorithm for an application.
5.4 Algorithmic Performance
When we discuss about algorithmic performance there are two aspects to be considered namely time and space requirements. Instructions of an algorithm take time to be executed. We generally discuss how fast the algorithm performs and what are the components that affect its runtime. The other aspect is the space requirement. In general, data structures take space to be represented and so the kind of data structures that can be used and how the choice of data structure affects the runtime are important considerations.
However in this module we will focus on the time aspect of algorithmic performance. In this case the main questions to be answered include how to estimate the time required to run an algorithm, how to reduce the time required for implementing an
| Example 5.1
A city has n stops. A bus driver wishes to follow the shortest path from one stop to another. Between every two stops, if a road exists, it may take a different time from other roads. Also, roads are one-way, i.e., the road from point 1 to 2, is different from that from point 2 to 1. How to find the shortest path between any two pairs?
A Naïve approach to the problem is to list all the paths (e) between a given pair of points and then compute the travel time for each. After this process we choose the shortest one.
The number of paths will be n!= (n/e )n It will be impossible to run your algorithm even for a value of n = 30
Figure 5.1 Example of Time Taken by an Algorithm |
algorithm by considering the factors affecting the running time including computer used, compiler and algorithm used and finally what is the input to the algorithm for implementing an algorithm by considering the factors affecting the running time including computer used, compiler and algorithm used and finally what is the input to the algorithm. We assume that in the machine model considered the instructions are executed one after another, with no concurrent operation that is we do not consider parallel computation. An example shows (Figure 5.1) the comparison of two algorithms. Let us consider another example (Figure 5.2).
| Example 5.2 – Selection Problem
Given a list of N numbers, we need to determine the kth largest, where k £ N. There are two algorithms which can accomplish the given task.
Algorithm 1: 1. Read N numbers into an array 2. Sort the array in decreasing order by some simple algorithm 3. Return the element in position k
Algorithm 2: 1. Read the first k elements into an array and sort them in decreasing order 2.Each remaining element is read one by one
3. The element in the kth position is returned as the answer.
Now the question is which algorithm is better when N =100 and k = 100? What happens when N = 1,000,000 and k = 500,000? Now the above two algorithms are not the only ones there exists better algorithms.
Figure 5.2 Examples of Two Algorithms for the Selection Problem |
5.5 Time Complexity
Time complexity is a function that specifies how the running time of an algorithm depends on the size of the input.
5.5.1 Definition of Time
Now we have to understand the concept of time in the context of analyzing algorithms. Time can be defined as number of seconds. However this definition of time makes the analysis machine and implementation dependent. Another way to define time is in terms of the lines of code executed so that algorithms performance can be compared independent of the machine used and the actual implementation methodology. It can also be defined as the number of times a specific operation is performed, example being the number of times addition is performed.
5.5.2 Running-time of algorithms
The time bounds that we define are for the algorithms and not for programs. Programs are just implementations of an algorithm, and almost always the details of the program do not affect the bounds since they are defined in a relative manner. Similarly bounds are for algorithms not for the problems the algorithms solve. A problem can be solved with several algorithms, some are more efficient than others and have different bounds.
5.5.3 Efficiency of an algorithm
Normally when we want to analyze an algorithm we do not consider the actual run time using the computer. This running time is basically machine dependent. The solution to the problem is to carry out machine independent analysis. We also make the simplifying assumption that every basic operation takes constant time. Examples of such basic operations include addition, subtraction, multiplication, memory access operations. Non-basic operations such as sorting, searching, etc. are normally defined using basic operations. The efficiency of an algorithm is the number of basic operations it performs. In fact we do not distinguish between the basic operations for the purpose.
5.5.4 Theoretical analysis of time efficiency
Time efficiency is analyzed by determining the number of repetitions of the basic operation as a function of input size. Basic operation is defined as the operation that has the most influence in determining the running time of the algorithm. However different basic operations may cost differently. Figure 5.4 shows that running time of an algorithm is defined in terms of the input size and is the product of the execution time of a basic operation and the number of times the basic operation is executed.
Figure 5.4 Running time
The table shown in Figure 5.5 shows the input size and basic operation for different problems.
Figure 5.5 Examples of Input Size and basic operations
For example, when analysing the worst case running time of a function that sorts a list of numbers, we are interested in determining the time taken in terms of the length of the input list and expressed as a function of this length. For example, the standard insertion sort takes time T(n) where T(n)= c*n2+k for some constants c and k.
In fact, we do not worry about the exact values, but will look at “broad classes’ of values, or the growth rates. In case we consider the size of the input to be n. If an algorithm needs n basic operations and another algorithm needs 2n basic operations, we will consider them to be in the same efficiency category. However, we distinguish between exp(n), n, log(n).
5.6 Asymptotic Algorithm Analysis
The asymptotic analysis of an algorithm determines the running time in big-Oh notation. To perform the asymptotic analysis we first determine the worst-case or maximum number of primitive operations executed in terms of the function of the input size. We express this function with big-Oh notation. Since constant factors and lower-order terms will eventually be dropped, we can ignore them when counting the number of primitive operations. When we express the running time of an algorithm as T(n), we mean that T(n) is an upper bound on the running time that holds for all inputs of size n. This is called worst-case analysis. The algorithm may take less time on some inputs of size n, but we consider the worst case.
5.6.1 Asymptotic growth rate
The asymptotic behaviour of a function f(n) (such as f(n)=c*n or f(n)=c*n2, etc.) refers to the growth of f(n) as n gets large. In general we are not interested in small values of n, since what is crucial is the estimation of how slow the performance of the program will be on large inputs. The slower the asymptotic growth rate, the better the algorithm. Therefore we need a method of comparing functions that ignores constant factors and small input sizes. Before we go further let us some define some classes of functions.
• O(g(n)): class of functions f(n) that grow no faster than g(n) – Big Oh
• Θ (g(n)): class of functions f(n) that grow at same rate as g(n) – Big Theta
• Ω(g(n)): class of functions f(n) that grow at least as fast as g(n) – Big Omega In general we use Big-Oh notation in the context of time analysis of algorithms.
5.6.2 Asymptotic notation: Big-Oh
In estimating the running time of an algorithm we do not know the values constants associated with the function. A convenient notation for hiding the constant factor is the Big-Oh notation such as O(n) (read: ”order n”) instead of ”cn for some constant c.” Thus an algorithm is said to be O(n) or linear time if there is a fixed constant c such that for all sufficiently large n, the algorithm takes time at most cn on inputs of size n. An algorithm is said to be O(n2) or quadratic time if there is a fixed constant c such that for all sufficiently large n, the algorithm takes time at most cn2 on inputs of size n. O(1) means constant time. The Big-Oh notation is a notation that concisely captures the important differences in the asymptotic growth rates of functions. One important advantage of big-O notation is that it makes algorithms much easier to analyse, since we can conveniently ignore low order terms. For example, an algorithm that runs in time say 16n3 + 20n2 + 4n log n + 100 is still a considered as a cubic algorithm of the order O( n3). This means that any two linear algorithms will be considered equally good by this measure. This is one of the main issues associated with asymptotic analysis and big-O notation. In summary in the case of Big-Oh notation to simplify the running time estimation, for a functionf(n), we ignore the constants and lower order terms.
5.6.3 Growth-Rate Functions
Now let us discuss some typical growth rate functions in the context of analysis of algorithms.
O(1) –that of the order of 1 – here time requirement is constant, which means the time taken by the algorithm is independent of the size of the problem.
O(log2n) –that is of the order of logn – here the time requirement has logarithmic growth in terms of n ( size of the problem) and increases slowly as the problem size increases.
O(n) – that is of the order n – here the time requirement has linear growth in terms of the size of the problem n and increases directly with the size of the problem.
O(n*log2n) – that is of the order of nlogn that is the time requirement has a growth of nlogn and increases more rapidly than a linear algorithm.
O(n2) – that is of the order of n2- here the time requirement has quadratic growth in terms of the size of the problem n and increases rapidly with the size of the problem.
O(n3) – that is of the order of n3- here the time requirement has cubic growth in terms of the size of the problem n and increases very rapidly with the size of the problem.
O(2n) – that is of the order of 2n – here as the size of the problem increases, the time requirement experiences an exponential growth and increases too rapidly to be practical.
A Comparison of Growth-Rate Functions is shown in Figure 5.5
5.7 Primitive Operations
The basic computations performed by an algorithm are identifiable in pseudocode. However an algorithm is specified such that these operations are largely independent from the programming language. The exact definition of the operations is not important. It is assumed to take a constant amount of time in the RAM model. The RAM model is used for the purpose of analysis and is assumed to have one processor, execute one instruction at a time where each instruction takes “unit time“, has fixed-size operands, and has fixed size storage (RAM and disk).
Examples of these basic operations include:
- Evaluating an expression
- Assigning a value to a variable
- Indexing into an array
- Calling a method
- Returning from a method
Now let us consider an example shown in Figure 5.6. As can be seen from the example for for loops the maximum time required is at most the running time of the statements inside the for-loop (including tests) times the number of iterations.
Figure 5.6. An example showing the Calculation of Time Complexity
In the case nested for loops (shown in example in Figure 5.7) the running time of the statement multiplied by the product of the sizes of all the for-loops and hence will result in time complexity of the order of O(N 2)
Consecutive statements just add to the overall time complexity. If there are n such statements then they add to the time complexity of nested for loops.
O(N) + O(N2) = O(N2)
In the case of If/Else statements the time complexity is never more than the running time of the test plus the larger of the running times of S1 and S2 where S1 is the set of statements in the then part of If/Else and S2 is the set of statements in the else part of If/Else
5.8 Best-case, average-case, worst-case
Now let us discuss the various cases of time complexity analysis. We have already discussed that in most cases we try to find out the worst case time complexity. But in this section we will discuss this and other cases. These three cases arise because not all inputs of a given size take the same time to run.
• Worst case: W(n) – maximum over inputs of size n – this is the maximum time complexity for the given input size. Worst-case running time of an algorithm is the longest running time for any input of size n. In other words it is an upper bound on the running time for any input and in fact guarantees that the algorithm will never take longer than this time. Example: Sort a set of numbers in increasing order; and the data is in decreasing order. Nevertheless the worst case can occur fairly often
• Best case: B(n) – minimum over inputs of size n
• Average case:A(n)– “average” over inputs of size n. We can calculate the average case complexity under some assumption about the probability distribution of all possible inputs of size n, and calculate the weighted sum of expected C(n) (numbers of basic operation repetitions) over all possible inputs of size n.
Let us consider an example of sequential search (Figure 5.8) and another example for searching a database (Figure 5.9) to illustrate these aspects.
| Sequential search for K in an array of n integers:
Begin at first element in array and look at each element in turn until K is found
• Best case: Find at first position. Cost is 1 for the comparison operation . • Worst case: Find at last position. Cost is n compares. • Average case: (n+1)/2 compares IF we assume the element with value K is equally likely to be in any position in the array.
Figure 5.8 Sequential Search in an Array |
E.g. Sorting the elements in an array
Figure 5.9 Sorting the Elements in an Array |
5.9 Recursive Algorithms: Analysis
We have already discussed how to analyze the running time of (iterative) algorithms. However in order to analyze recursive algorithms, we require more sophisticated techniques. Specifically, we study how to define and solve recurrence relations. We use the example of Factorial (Figure 5.10) to explain these concepts.
In order to analyze the recursive algorithm we need to find out the number of multiplications performed by the factorial F(n)? When n=1 we do not perform any multiplication. In other cases we perform one plus how many ever multiplications we perform in the recursive call (Factorial(n-1)). The number of multiplications can be expressed as a formula
F(0) = 0
F(n) = 1 + F(n-1)
This relation is known as a recurrence relation.
5.10 Recurrences and Running Time
Now let us discuss how to find out the running time in terms of recurrence equations. A recurrence equation gives a function of a value n in terms of functions on smaller inputs (lesser than n). This is given below:
T(n) = T(n-1) + n
Recurrences arise when an algorithm contains recursive calls to itself. Now we need to find out the actual running time of the algorithm. In order to do this we need to solve the recurrence equation by finding an explicit formula of the expression by binding the recurrence by an expression that involves n. Let us understand this using the example of Binary Search (Figure 5.11) and the corresponding algorithm (Figure 5.12).
Figure 5.12 Binary Search Algorithm
Now let us discuss the recurrence equation for the above binary search algorithm. The algorithm can be analysed as given. O(1) is the time taken to do the comparisons. After this process the search range is divided into two halves. Therefore
T(N) = T(N/2) + 1
On applying the recurrence repeatedly we get
T(N) = T(N/4) + 2
= T(N/8) + 3 …
= T(N/2k) + k
Let this be rounded to nearest power of 2. That is let N≤2m.
T(N) ≤ T(2m/2k)+k
Let k = m.
Then T(N) ≤ T(2m/2m)+m = T(1)+m = 1+m = O(m)
If N=2m, then m=log N. So T(N) = O(log N)
Thus, the running time is O(log N)
Summary
- Discussed the analysis of algorithms and the need for such analysis
- Understood the concept of time complexity and how it can be estimated
- Explained the use of recurrence equation for analysing recursive algorithms
| you can view video on Analysis of Algorithms | |
