Data Structures and
Algorithms
Lecture - Algorithms
Amir Ali
[Link]@[Link]
Algorithms !
Old Women Problems !
Outline
Introduction
Algorithms
Algorithms
Classification of Algorithms
Classification of Algorithms
Specifications of Algorithms
Specifications of Algorithms
Specifications of Algorithms
Specifications of Algorithms
Algorithm Analysis
Algorithm Analysis
Algorithm Analysis
Algorithm Growth Rate
Algorithm Growth Rate
Big Oh (O) – used to calculate the maximum time taken by an algorithm to execute
completely.
Big Theta (Θ) – used to calculate the average time taken by an algorithm to execute
completely.
Algorithm Growth Functions
Algorithm Growth Functions
Algorithm Growth Functions
Algorithm Growth Functions
Algorithm Growth Functions
Algorithm Growth Functions
The Big – oh Rules
Algorithm Growth Rate -
Example
Let’s take an example to understand this
process –
Let’s denote the value of time complexity by Tn,
then –
Tn = C1 + C2(n+1) + nC3 + C1
= C1 + nC2 + C2 + nC3 + C1
Tn = n(C2+C3) + 2C1
Look like a linear equation y = mx
In depth Running Time Analysis
In depth Running Time Analysis
Space Analysis
Assignment and Quiz !
Calculate and explain the time complexity of
the following
var a = code
0, b = 0, i, j, k, N;
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
a = a + j;
}
}
for (k = 0; k < N; k++) {
b = b + k;
}