In the last post I told you about data structures and algorithms. In this post we will see how can we do the analysis of algorithm. I write all my posts are in question and answer format I hope you can understand what I am trying to explain to you but if anyone have any doubts/question please do ask it in comments column and in case if you like my posts please share it on Facebook or tell your friends about it.
What is an algorithm? An algorithm is a step-by-step instruction to a given problem
.
Why do we do analysis of algorithm? Suppose we want to go from city A to city B. There are many ways of doing this: by flight,by bus, by train and also by cycle. Depending on the availability and convenience we choose the one which suits us. Similarly in computer science there can be many algorithms there can be many algorithms that exist for solving the same problem(for example sorting algorithm has lot of algorithms like insertion sort, selection sort, quick sort and many more). Algorithm analysis help us determine which of them is efficient in terms of time and space consumed.
What are the goals of analyzing and algorithm? The goal of analysis of algorithm is to compare algorithms/solutions mainly in terms of running time but also in terms of other factors(e.g memory, developer's effort etc).
What is running time analysis? It is the process to determine how processing time increases as the size of the problem(input size) increases. Input size is the number of elements in the input and depending on the problem type the input may be of different types.
How to compare algorithms? If we express running time of a given algorithm as a function of input size n(i.e, f(n) ) we can compare these different functions corresponding to running time and this kind of comparison is independent of machine time,programming style etc.
What is rate of growth? The rate at which running time increases as the function of input is called rate of growth.
What are different type of analysis?There are three different type of analysis and these are:
1.worst case analysis:
What is an algorithm? An algorithm is a step-by-step instruction to a given problem
.
Why do we do analysis of algorithm? Suppose we want to go from city A to city B. There are many ways of doing this: by flight,by bus, by train and also by cycle. Depending on the availability and convenience we choose the one which suits us. Similarly in computer science there can be many algorithms there can be many algorithms that exist for solving the same problem(for example sorting algorithm has lot of algorithms like insertion sort, selection sort, quick sort and many more). Algorithm analysis help us determine which of them is efficient in terms of time and space consumed.
What are the goals of analyzing and algorithm? The goal of analysis of algorithm is to compare algorithms/solutions mainly in terms of running time but also in terms of other factors(e.g memory, developer's effort etc).
What is running time analysis? It is the process to determine how processing time increases as the size of the problem(input size) increases. Input size is the number of elements in the input and depending on the problem type the input may be of different types.
How to compare algorithms? If we express running time of a given algorithm as a function of input size n(i.e, f(n) ) we can compare these different functions corresponding to running time and this kind of comparison is independent of machine time,programming style etc.
What is rate of growth? The rate at which running time increases as the function of input is called rate of growth.
What are different type of analysis?There are three different type of analysis and these are:
1.worst case analysis:
- defines the input for which algorithm takes huge time
- input is the one for which algorithm runs slower.
- defines the input for which algorithm takes the lowest time
- Input is the one for which algorithm runs the fastest.
- provides the prediction about running time of algorithm.
- Assumes that input is random.
Time complexity
How long does this sorting program run? It possibly takes a very long time on large inputs (that is many strings) until the program has completed its work and gives a sign of life again. Sometimes it makes sense to be able to estimate the running time before starting a program. Nobody wants to wait for a sorted phone book for years! Obviously, the running time depends on the number n of the strings to be sorted. Can we find a formula for the running time which depends on n?Having a close look at the program we notice that it consists of two nested for-loops. In both loops the variables run from 0 to n, but the inner variable starts right from where the outer one just stands. An if with a comparison and some assignments not necessarily executed reside inside the two loops. A good measure for the running time is the number of executed comparisons. In the first iteration n comparisons take place, in the second n-1, then n-2, then n-3 etc. So 1+2+...+n comparisons are performed altogether. According to the well known Gaussian sum formula these are exactly 1/2·(n-1)·n comparisons. Figure 2.8 illustrates this. The screened area corresponds to the number of comparisons executed. It apparently corresponds approx. to half of the area of a square with a side length of n. So it amounts to approx. 1/2·n2.
How does this expression have to be judged? Is this good or bad? If we double the number of strings to be sorted, the computing time quadruples! If we increase it ten-fold, it takes even 100 = 102 times longer until the program will have terminated! All this is caused by the expression n2. One says: Sorting by minimum search has quadratic complexity. This gives us a forefeeling that this method is unsuitable for large amounts of data because it simply takes far too much time.
So it would be a fallacy here to say: “For a lot of money, we'll simply buy a machine which is twice as fast, then we can sort twice as many strings (in the same time).” Theoretical running time considerations offer protection against such fallacies.
The number of (machine) instructions which a program executes during its running time is called its time complexity in computer science. This number depends primarily on the size of the program's input, that is approximately on the number of the strings to be sorted (and their length) and the algorithm used. So approximately, the time complexity of the program “sort an array of n strings by minimum search” is described by the expression c·n2.
c is a constant which depends on the programming language used, on the quality of the compiler or interpreter, on the CPU, on the size of the main memory and the access time to it, on the knowledge of the programmer, and last but not least on the algorithm itself, which may require simple but also time consuming machine instructions. (For the sake of simplicity we have drawn the factor 1/2 into c here.) So while one can make c smaller by improvement of external circumstances (and thereby often investing a lot of money), the term n2, however, always remains unchanged.
In other words: c is not really important for the
description of the running time! To take this circumstance into
account, running time complexities are always specified in the
so-called O-notation
in computer science. One says: The sorting method has running
time O(n2). The
expression O is also called Landau's symbol.
Mathematically speaking, O(n2) stands for a set of functions, exactly for all those functions which, “in the long run”, do not grow faster than the function n2, that is for those functions for which the function n2 is an upper bound (apart from a constant factor.) To be precise, the following holds true: A function f is an element of the set O(n2) if there are a factor c and an integer number n0 such that for all n equal to or greater than this n0 the following holds:
The function n2 is then called an
asymptotically upper
bound for f. Generally, the notation f(n)=O(g(n)) says that the function f is
asymptotically bounded from above by the function
g.
A function f from O(n2) may grow considerably more slowly than n2 so that, mathematically speaking, the quotient f / n2 converges to 0 with growing n. An example of this is the function f(n)=n. However, this does not hold for the function f which describes the running time of our sorting method. This method always requires n2 comparisons (apart from a constant factor of 1/2). n2 is therefore also an asymptotically lower bound for f. This f behaves in the long run exactly like n2. Expressed mathematically: There are factors c1 and c2 and an integer number n0 such that for all n equal to or larger than n0 the following holds:
So f is bounded by n2 from above
and from below. There also is a notation of its
own for the set of these functions: Θ(n2).
Figure contrasts a function f which is bounded from above by O(g(n)) to a function whose asymptotic behavior is described by Θ(g(n)): The latter one lies in a tube around g(n), which results from the two factors c1 and c2.
Thereby we can estimate the order of magnitude of the method used; in general, however, we cannot make an exact running time prediction. (Because in general we do not know c, which depends on too many factors, even if it can often be determined experimentally.
Frequently the statement is found in the manual that an operation takes “constant time”. By this it is meant that this operation is executed with a constant number of machine instructions, independently from the size of the input. The function describing the running time behavior is therefore in O(1). The expressions “linear time” and “logarithmic time” describe corresponding running time behaviors: By means of the O-notation this is often expressed as “takes time O(n) and O(log(n))”, respectively.
Furthermore, the phrase “expected time” O(g(n)) often appears in the manual. By this it is meant that the running time of an operation can vary from execution to execution, that the expectation value of the running time is, however, asymptotically bounded from above by the function g(n).
Back to our sorting algorithm: A runtime of Θ(n2) indicates that an adequately big input will always bring the system to its knees concerning its running time. So instead of investing a lot of money and effort in a reduction of the factor c, we should rather start to search for a better algorithm.
To give an example, we read on the manual page of array in the section “Implementation” that the method sort() of arrays implements the known Quicksort algorithm whose (expected) complexity is O(n·log(n)) which (seen asymptotically) is fundamentally better than Θ(n2). This means that Quicksort defeats sorting by minimum search in the long run: If n is large enough, the expression c1·n·log(n) certainly becomes smaller than the expression c2·n2, independently from how large the two system-dependent constants c1 and c2 of the two methods actually are; the quotient of the two expressions converges to 0. (For small n, however, c1·n·log(n) may definitely be larger than c2·n2; indeed, Quicksort does not pay on very small arrays compared to sorting by minimum search.)
Now back to the initial question: Can we sort phone books with our sorting algorithm in acceptable time? This depends, in accordance to what we said above, solely on the number of entries (that is the number of inhabitants of the town) and on the system-dependent constant c. Applied to today's machines: the phone book of Saarbrücken in any case, the one of Munich maybe in some hours, but surely not the one of Germany. With the method sort() of the class array, however, the last problem is not a problem either.
Mathematically speaking, O(n2) stands for a set of functions, exactly for all those functions which, “in the long run”, do not grow faster than the function n2, that is for those functions for which the function n2 is an upper bound (apart from a constant factor.) To be precise, the following holds true: A function f is an element of the set O(n2) if there are a factor c and an integer number n0 such that for all n equal to or greater than this n0 the following holds:
f(n) ≤ c·n2.
A function f from O(n2) may grow considerably more slowly than n2 so that, mathematically speaking, the quotient f / n2 converges to 0 with growing n. An example of this is the function f(n)=n. However, this does not hold for the function f which describes the running time of our sorting method. This method always requires n2 comparisons (apart from a constant factor of 1/2). n2 is therefore also an asymptotically lower bound for f. This f behaves in the long run exactly like n2. Expressed mathematically: There are factors c1 and c2 and an integer number n0 such that for all n equal to or larger than n0 the following holds:
c1·n2 ≤ f(n)
≤ c2·n2.
Figure contrasts a function f which is bounded from above by O(g(n)) to a function whose asymptotic behavior is described by Θ(g(n)): The latter one lies in a tube around g(n), which results from the two factors c1 and c2.
Thereby we can estimate the order of magnitude of the method used; in general, however, we cannot make an exact running time prediction. (Because in general we do not know c, which depends on too many factors, even if it can often be determined experimentally.
Frequently the statement is found in the manual that an operation takes “constant time”. By this it is meant that this operation is executed with a constant number of machine instructions, independently from the size of the input. The function describing the running time behavior is therefore in O(1). The expressions “linear time” and “logarithmic time” describe corresponding running time behaviors: By means of the O-notation this is often expressed as “takes time O(n) and O(log(n))”, respectively.
Furthermore, the phrase “expected time” O(g(n)) often appears in the manual. By this it is meant that the running time of an operation can vary from execution to execution, that the expectation value of the running time is, however, asymptotically bounded from above by the function g(n).
Back to our sorting algorithm: A runtime of Θ(n2) indicates that an adequately big input will always bring the system to its knees concerning its running time. So instead of investing a lot of money and effort in a reduction of the factor c, we should rather start to search for a better algorithm.
To give an example, we read on the manual page of array in the section “Implementation” that the method sort() of arrays implements the known Quicksort algorithm whose (expected) complexity is O(n·log(n)) which (seen asymptotically) is fundamentally better than Θ(n2). This means that Quicksort defeats sorting by minimum search in the long run: If n is large enough, the expression c1·n·log(n) certainly becomes smaller than the expression c2·n2, independently from how large the two system-dependent constants c1 and c2 of the two methods actually are; the quotient of the two expressions converges to 0. (For small n, however, c1·n·log(n) may definitely be larger than c2·n2; indeed, Quicksort does not pay on very small arrays compared to sorting by minimum search.)
Now back to the initial question: Can we sort phone books with our sorting algorithm in acceptable time? This depends, in accordance to what we said above, solely on the number of entries (that is the number of inhabitants of the town) and on the system-dependent constant c. Applied to today's machines: the phone book of Saarbrücken in any case, the one of Munich maybe in some hours, but surely not the one of Germany. With the method sort() of the class array, however, the last problem is not a problem either.
The better the time complexity of an algorithm is, the
faster the algorithm will carry out his work in
practice. Apart from time complexity, its space complexity is also
important: This is essentially the number of memory cells
which an algorithm needs. A good algorithm keeps this number
as small as possible, too.
There is often a time-space-tradeoff involved in a problem, that is, it cannot be solved with few computing time and low memory consumption. One then has to make a compromise and to exchange computing time for memory consumption or vice versa, depending on which algorithm one chooses and how one parameterizes it.
There is often a time-space-tradeoff involved in a problem, that is, it cannot be solved with few computing time and low memory consumption. One then has to make a compromise and to exchange computing time for memory consumption or vice versa, depending on which algorithm one chooses and how one parameterizes it.
Posts
