Algorithms. Introduction.

Introduction

Analysis of Algorithms

Some reasons to perform mathematical analysis:

To compare different algorithms for the same task
To predict performance in a new environment
To set values of algorithm parameters

Some important factors in precise analysis that are usually outside a given programmer's domain influence

C++ programs are translated into machine code for a given computer, and it can be a challenging task to compute the exact time needed to execute even one statement.
Many programs are sensitive to their input data, and performance usually depends on the input.
Many programs of interest are not yet well understood (no specific mathematic results).
Two programs might not be comparable at all (f.e. depending on the input their work with great difference in performance).

The analysis amounts to determine the frequency of execution of a few fundamental operations:

assigning a value to a variable;
calling a function;
performing an arithmetic operation;
comparing two numbers;
following a pointer reference (accessing an array element).

In this course we will be to look for rough estimates of these quantities.

We also have to study the data, and to model the input that might be presented to the algorithm. Most often, we consider one of two approaches to the analysis:

we either assume that the input is random, and study the average-case performance
or we look for perverse input, and study the worst-case performance.

How fast functions grow and big-O notation

Most algorithms have a primary parameter N that affects the running time most significantly. This parameter may be the size of the array to sort or search in, the size of the file, the degree of a polynomial, number of vertices in a graph, number of characters in a string, etc. While estimating efficiency of an algorithm, our goal is to express the resources requirements of it in terms of N. In the table we can see some functions that are convenient to use for estimation of algorithms discussed in this course.

Function Description Graph

1 Most instructions of most programs are executed once or at most only a few times. If all the instructions of a program have this property, we say that the program's running time is constant. N/A

log(N) When the running time of a program is logarithmic, the program gets slightly slower as N grows. This running time commonly occurs in programs that solve a big problem by transformation into a series of smaller problems, cutting the problem size by some constant fraction at each step.

N When the running time of a program is linear, it is generally the case that a small amount of processing is done on each input element. That is, whenever N, doubles so does the running time.

N*log(N) This timing arises usually when algorithm solves a problem by breaking it up into smaller subproblems, solving them independently, and then combining the solutions. (When N doubles, then the running time more [but not much more] than doubles.)

N² When the running time is quadratic, that algorithm is practical only for use on only relatively small problems because when N doubles, the running time increases fourfold.

2^N Very few algorithms with exponential time are likely to be appropriate for practical use, even though such algorithms arise natuarally as brute-force solution to problems. Whenever N doubles, the running time squares!

Function	Description	Graph
1	Most instructions of most programs are executed once or at most only a few times. If all the instructions of a program have this property, we say that the program's running time is constant.	N/A
log(N)	When the running time of a program is logarithmic, the program gets slightly slower as N grows. This running time commonly occurs in programs that solve a big problem by transformation into a series of smaller problems, cutting the problem size by some constant fraction at each step.
N	When the running time of a program is linear, it is generally the case that a small amount of processing is done on each input element. That is, whenever N, doubles so does the running time.
Nlog(N)*	This timing arises usually when algorithm solves a problem by breaking it up into smaller subproblems, solving them independently, and then combining the solutions. (When N doubles, then the running time more [but not much more] than doubles.)
N²	When the running time is quadratic, that algorithm is practical only for use on only relatively small problems because when N doubles, the running time increases fourfold.
2^N	Very few algorithms with exponential time are likely to be appropriate for practical use, even though such algorithms arise natuarally as brute-force solution to problems. Whenever N doubles, the running time squares!

The following table shows how much time it takes to solve huge problems on machines of different speed.

Operations
per
seconds Problem size 1 million Problem size 1 billion

N N*log(N) N² N N*log(N) N²

10⁶ seconds seconds weeks hours hours never

10⁹ instant instant hours seconds seconds decades

10¹² instant instant seconds instant instant weeks

Operations per seconds	Problem size 1 million	Problem size 1 billion
N	Nlog(N)*	N²	N	Nlog(N)*	N²
10⁶	seconds	seconds	weeks	hours	hours	never
10⁹	instant	instant	hours	seconds	seconds	decades
10¹²	instant	instant	seconds	instant	instant	weeks

Big-O notation

Definition: A function g(N) is said to be O(f(N)) if there exists constant c₀ such that

g(N) < c₀ O(f(N))

for all N greater than some N₀.

In this course this notation basically will be used to say that one function is approximately equal another (usually simpler) function when parameter N is large. For example, we can say that

3*N² + 2*N - N*log²(N)

is approximately the same as 3*N² if N is big enough. That is, we can say that 3*N² + 2*N = O(N²).

For more details see this page.

More details on these topics can be found in the second chapter of Algorithms in C++ from Robert Sedgewick.