Analysis of Algorithms

Professor: Wilson Soto

Colombia

2019

Algorithms 2019
 Algorithm

An algorithm is any well-defined computational procedure that takes some value,

or set of values, as input and produces some value, or set of values, as output. An
algorithm is thus a sequence of computational steps that transform the input into
the output.

Algorithms 2019 1
 Why Analyze an Algorithm?

The most straightforward reason for analyzing an algorithm is to discover its

characteristics in order to evaluate its suitability for various applications or compare
it with other algorithms for the same application. Moreover, the analysis of an
algorithm can help us understand it better, and can suggest informed improvements.
Algorithms tend to become shorter, simpler, and more elegant during the analysis
process.

Algorithms 2019 2
 Computational Complexity

The branch of theoretical computer science where the goal is to classify

algorithms according to their efficiency and computational problems according to
their inherent difficulty is known as computational complexity.

Algorithms 2019 3
 Analysis of Algorithms

A complete analysis of the running time of an algorithm involves the following

steps:

1. Implement the algorithm completely.

2. Determine the time required for each basic operation.

3. Identify unknown quantities that can be used to describe the frequency of

execution of the basic operations.

Algorithms 2019 4
 Analysis of Algorithms (cont.)

1. Develop a realistic model for the input to the program.

2. Analyze the unknown quantities, assuming the modelled input.

3. Calculate the total running time by multiplying the time by the frequency for
each operation, then adding all the products.

Algorithms 2019 5
 The running time

The running time of an algorithm on a particular input is the number of primitive

operations or “steps” executed.

Usually, the analysis of algorithms is concentrate on finding only the worst-case

running time.

The worst-case running time of an algorithm gives us an upper bound on the

running time for any input. Knowing it provides a guarantee that the algorithm
will never take any longer.

Algorithms 2019 6
 Order of growth

We usually consider one algorithm to be more efficient than another if its

worst-case running time has a lower order of growth.

Algorithms 2019 7
 Asymptotic notation

The notations we use to describe the asymptotic running time of an algorithm

are defined in terms of functions whose domains are the set of natural numbers
N = {0, 1, 2, . . .}. Such notations are convenient for describing the worst-case
running-time function T (n), which usually is defined only on integer input sizes.

Algorithms 2019 8
 O-notation

Definition 1. For a given function g(n), we denote by O(g(n)) the set of functions:

O(g(n)) = {f (n) | ∃c > 0, ∃n0 > 0, ∀n ≥ n0 : 0 ≤ f (n) ≤ cg(n)}

Algorithms 2019 9
 Ω-notation

Definition 2. For a given function g(n), we denote by Ω(g(n)) the set of functions:

Ω(g(n)) = {f (n) | ∃c > 0, ∃n0 > 0, ∀n ≥ n0 : 0 ≤ cg(n) ≤ f (n)}

Algorithms 2019 10
 Θ-notation

Definition 3. For a given function g(n), we denote by Θ(g(n)) the set of functions:

Θ(g(n)) = {f (n) | ∃c1 > 0, ∃c2 > 0, ∃n0 > 0, ∀n ≥ n0 : 0 ≤ c1g(n) ≤ f (n) ≤ c2g(n)}

Algorithms 2019 11
Algorithms 2019 12
 Fibonacci Numbers

Draw the behaviour of the algorithms to get the n-th Fibonacci number.

The Fibonacci numbers are the numbers in the following integer sequence.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, . . .

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the

recurrence relation

Fn = Fn−1 + Fn−2

with seed values

F0 = 0 and F1 = 1

Algorithms 2019 13
 Fibonacci Numbers

Given a number n, print n-th Fibonacci Number. Examples:

Input : n = 2
Output : 1

Input : n = 9
Output : 34

Signature in Java:

interface Funcion {
int fib (int n);
}

Algorithms 2019 14
 Fibonacci Numbers (Method 1 - Recursion)

class Recursion implements Funcion {

int fib(int n) {
if (n <= 1) return n;
else return fib(n-1) + fib(n-2);
}
}

Time Complexity: T (n) = T (n − 1) + T (n − 2) which is exponential.

Algorithms 2019 15
 Fibonacci Numbers (Method 2 - Dynamic Programming)

class DP implements Funcion {

int fib(int n) {
int f[] = new int[n+2];
int i;
f[0] = 0;
f[1] = 1;
for (i = 2; i <= n; i++)
f[i] = f[i-1] + f[i-2];

return f[n];
}
}

Time Complexity: O(n)

Algorithms 2019 16
 Fibonacci Numbers (Method 3 - Space Optimized Method)

class SpaceOpt implements Funcion {

int fib(int n) {
int a = 0, b = 1, c;
if (n == 0) return a;
for (int i = 2; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
return b;
}
}

Time Complexity: O(n)

Algorithms 2019 17
 Fibonacci Numbers (Method 4 - Power of the matrix
{{1,1},{1,0}})

class Power implements Funcion {

int fib(int n) {
int F[][] = new int[][]{{1,1},{1,0}};
if (n == 0) return 0;
power(F, n-1);

return F[0][0];
}

static void multiply(int F[][], int M[][]) {

int x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0];

Algorithms 2019 18
 int w = F[1][0]*M[0][1] + F[1][1]*M[1][1];

F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}

static void power(int F[][], int n) {

int i;
int M[][] = new int[][]{{1,1},{1,0}};

for (i = 2; i <= n; i++)

multiply(F, M);
}
}
Time Complexity: O(n)

Algorithms 2019 19
 Fibonacci Numbers (Method 5 - Optimized Power of the
matrix {{1,1},{1,0}})

class PowerOpt implements Funcion {

int fib(int n) {
int F[][] = new int[][]{{1,1},{1,0}};
if (n == 0) return 0;
power(F, n-1);

return F[0][0];
}

static void multiply(int F[][], int M[][]) {

int x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0];

Algorithms 2019 20
 int w = F[1][0]*M[0][1] + F[1][1]*M[1][1];

F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}

static void power(int F[][], int n) {

if ( n == 0 || n == 1) return;
int M[][] = new int[][]{{1,1},{1,0}};
power(F, n/2);
multiply(F, F);
if (n%2 != 0) multiply(F, M);
}
}
Time Complexity: O(log n)

Algorithms 2019 21
 Fibonacci Numbers (Method 6 - Formula)

class Matrix implements Funcion {

static int f[];
int fib (int n) {
if (n == 0) return 0;
if (n == 1 || n == 2) return (f[n] = 1);

if (f[n] != 0)
return f[n];

int k = (n & 1) == 1? (n + 1) / 2 : n / 2;

f[n] = (n & 1) == 1? (fib(k) * fib(k) +

fib(k - 1) * fib(k - 1))
: (2 * fib(k - 1) + fib(k)) * fib(k);

Algorithms 2019 22
 return f[n];
}
}

Time Complexity: O(log n)

Algorithms 2019 23
 Fibonacci Numbers (Method 7 - Formula)

class Formula implements Funcion {

int fib (int n) {
double phi = (1 + Math.sqrt(5)) / 2;
return (int) Math.round(Math.pow(phi, n)
/ Math.sqrt(5));
}
}

Time Complexity: O(1)

Algorithms 2019 24
 Analysis of Loops O(1)

Time complexity of a function (or set of statements) is considered as O(1) if it

does not contain loop, recursion and call to any other non-constant time function.

//set of non-recursive and non-loop statements

For example swap() function has O(1) time complexity.

A loop or recursion that runs a constant number of times is also considered as

O(1). For example the following loop is O(1).

// Here c is a constant
for (int i = 1; i <= c; i++) {
// some O(1) expressions
}

Algorithms 2019 25
 Analysis of Loops O(n)

Time Complexity of a loop is considered as O(n) if the loop variables is

incremented / decremented by a constant amount. For example following functions
have O(n) time complexity.

// Here c is a positive integer constant

for (int i = 1; i <= n; i += c) {
// some O(1) expressions
}

for (int i = n; i > 0; i -= c) {

// some O(1) expressions
}

Algorithms 2019 26
 Analysis of Loops O(nc)

Time complexity of nested loops is equal to the number of times the innermost
statement is executed. For example the following sample loops have O(n2) time
complexity

for (int i = 1; i <=n; i += c) {

for (int j = 1; j <=n; j += c) {
// some O(1) expressions
}
}

for (int i = n; i > 0; i -= c) {

for (int j = i+1; j <=n; j += c) {
// some O(1) expressions
}

Algorithms 2019 27
 Analysis of Loops O(log n)

Time Complexity of a loop is considered as O(log n) if the loop variables is

divided / multiplied by a constant amount.

for (int i = 1; i <=n; i *= c) {

// some O(1) expressions
}
for (int i = n; i > 0; i /= c) {
// some O(1) expressions
}

Algorithms 2019 28
 Analysis of Loops O(log log n)

Time Complexity of a loop is considered as O(log log n) if the loop variables is

reduced / increased exponentially by a constant amount.

// Here c is a constant greater than 1

for (int i = 2; i <=n; i = pow(i, c)) {
// some O(1) expressions
}
//Here fun is sqrt or cuberoot or any other constant root
for (int i = n; i > 0; i = fun(i)) {
// some O(1) expressions
}

Algorithms 2019 29
 Analysis of Loops - How to combine time complexities of
consecutive loops?

When there are consecutive loops, we calculate time complexity as sum of time
complexities of individual loops.

for (int i = 1; i <=m; i += c) {

// some O(1) expressions
}
for (int i = 1; i <=n; i += c) {
// some O(1) expressions
}

Time complexity of above code is O(m) + O(n) which is O(m + n), if m == n,

the time complexity becomes O(2n) which is O(n).

Algorithms 2019 30
 References

• Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, and Charles E. Leiserson.

Introduction to Algorithms (3rd ed.). McGraw-Hill Higher Education.

• Robert Sedgewick and Philippe Flajolet. An Introduction to the Analysis of

Algorithms. Addison-Wesley. 2011.

• https://www.geeksforgeeks.org/analysis-of-algorithms-set-4-analysis-of-loops/

Algorithms 2019 31