Algorithms & Data Structures - Algorithm analysis

OBJECTIVES

Understands what is algorithms analysis

Identify the reasons for conducting algorithm analysis

Obtain the basic mathematics background

Able to estimate the running time

Understand the efficiency of algorithm

Able to select the best algorithm for a program

What is algorithm analysis?

• The process of estimating the running time of an algorithm.
• Used to find the best algorithm to solve the problem.
• The role of algorithm analysis is to estimate the algorithm resource consumption.
• Algorithm analysis estimates the exact time and memory space required by an algorithm to solve a certain problem.

Algorithm Analysis --> Algorithm Efficiency

• less code
• economic
• less workload
• easy to maintain
• Faster to execute and get the result (speed)

How to conduct?

• Algorithm Analysis
• Empirical Analysis
• based on experimental Analysis
• Theoretical Analysis
• based on mathematical Analysis

Theoretical Analysis

• Use mathematical calculation
• Big–O notation
• Omega (Ω) notation

Big-O notation

Expressed as O(n) - On the Order of n

Instruction speed in loop

Program Structure	Big-O	Iterations	Estimate Time
Logarithmic	O(log n)	14	Microseconds
Linear	O(n)	10000	0.1 second
Linear Logarithmic	O(n(log n))	140000	2 seconds
Quadratic	O(n2)	100002	15 – 20 min

ALGORITHM EFFICIENCY

• Comparing two different algorithms that solve the same problem
• Algorithmics : “the systematic study of the fundamental techniques used to design and analyze efficient algorithms”
• Linear loops
• Logarithmic loops
• Linear logarithmic
• Dependent Quadratic
• Quadratic
• Best Case
• Worst Case
• Average case

CALCULATION Big O

• State the equation
• Remove the coefficients
• Keep the largest factor
• State in Big O notation

Exercises
Calculate the running time for this segment program
int i, j, p, q;
p = 5;
for (i = 0; i < 15; i++)
p = p + i;
q = 0;
for (j = 0; j < 60; j++)
q = q + j;

Calculate the running time for this segment program
int i, j, p, q;
p = 5;
for (i = 0; i < 30; i++)
for (j = 0; j < 60; j++)
p = p + i + j;
for (i = 0; i < 60; i++)
q = q * i + p;

Order the following function by growth rate:
n log2(n), n + n2, 24, n, √n, log2 n, 2n
Indicate which function grow at the same rate.

Calculate the running time for this segment program
Fun(int x)
{
if (x < 1)
return 1;
else
return (Fun(x - 2));

Calculate the running time

log(n) * n + 2n + log (n)

3n4 + 8n3/5 + 4

6 log(n) + 9n

3 n5/2 + n log(n)

6 log(n) + 7 log(n)