Data Structures - I
“No Bonus” marks for this course anymore
CP
CS
20
4
and say, O my Lord, Give me more knowledge.
(Quran 20 : 114)
1 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP
CS
20
4
Algorithm Analysis
Introduction
2 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Algorithm Analysis - Introduction
CS
• Efficiency
20
o Max # of 1’s
4 • O(n)
o Linear Search
• O(n)
o Binary Search
• O(log2 n)
o Sorted List Matching Problems
• O(n)
3 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Algorithm Analysis - Introduction
CS
• We will use Order Notation to approximate two
20 things about algorithms:
4 o How much time they take
o How much memory (space) they use
• Note:
o It is nearly impossible to figure out the exact amount of
time an algorithm will take
o Each algorithm gets translated into smaller and smaller
machine instructions
o Each of these instructions take various amounts of time
to execute on different computers
4 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Algorithm Analysis - Introduction
CS
• We want to judge algorithms independent of
20 their implementation
4 • Specifically
o we want to know how the performance of an
algorithm responds to changes in problem size
• And, rather than figure out an algorithm’s exact
running time
o We only want an approximation
o Big-O approximation
5 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Algorithm Analysis - Introduction
CS • Big – O Approximation
20 o After analyzing an algorithm, we end up with
4 • Polynomial equation/function
f (n) 4n 2 3n 10
o Growth of the function
n 4n2 3n 10
1 4 3 10
10 400 30 10
100 40,000 300 10
1000 4,000,000 3,000 10
10,000 400,000,000 30,000 10
100,000 40,000,000,000 300,000 10
1,000,000 4,000,000,000,000 3,000,000 10
6 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Algorithm Analysis - Introduction
CS • Big – O Approximation f (n) 4n 2 3n 10
20 o Efficiency is approximated by highest order term
4 • 4n2
o Eliminate all lower order terms
• 3n + 10
o Ignore all coefficient constants too
• 4 (from 4n2)
o Hence
f (n) 4n 2 3n 10
7 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Algorithm Analysis - Introduction
CS • Big – O Approximation
20 o f(n) = 4n2 +3n +10
• O(n2)
4 o f(n) = 76,756,234n2 + 427,913n + 7
• O(n2)
o f(n) = 74n8 - 62n5 - 71562n3 + 3n2 – 5
• O(n8)
o f(n) = 42n4*(12n6 - 73n2 + 11)
• O(n10)
o f(n) = 75n*logn – 415
• O(n*logn)
8 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Big–Oh - Introduction
CS
• 4n2 + 3n + 10 = O(n2)
20
4 • We have one function:
o f(n) = 4n2 + 3n + 10
• Let us make a second function, g(n)
o g(n) = n2
• So now we have
o f(n) = O (g(n))
9 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Big–Oh – Introduction (formal definition)
CS
g n f n : there exist positive constants c and no such that
20
0 f n cg n for all n n o
4
• c * g(n) is an upper
bound on the value of
f(n)
• Such that
• f(n) <= c * g(n)
10 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Common Order – Introduction
CS
• Complexity Classes Function Name
20
4 • The best running time 1 Constant
o1 log n Logarithmic
n Linear
• The Worst running time n log n Poly-log
o n!
n2 Quadratic
n3 Cubic
2n Exponential
n! Factorial
11 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Complexity Classes – O(1)
CS
• It is a notation for “constant work”
20
4 • An example would be finding the smallest
element in a sorted array
o There’s nothing to search for here
o The smallest element is always at the
beginning of a sorted array
o So this would take O(1) time
12 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Complexity Classes – O(n)
CS
• It means that the work changes in a way that
20 is proportional to n
4
• Example:
o If the input size doubles, the running time also
doubles
• It is a notation for “work grows at a linear
rate”
• You usually can’t really do a lot better than
this for most problems we deal with
13 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Complexity Classes – O(n ) k
CS
• O(n2) or “Order n2 ”: Quadratic time
20
o If input size doubles, running time increases by
4 a factor of 4
• O(n3) or “Order n3 ”: Cubic time
o If input size doubles, running time increases by
a factor of 8
• O(nk): Other polynomial time
o Should really try to avoid high order
polynomial running times
14 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Complexity Classes – O(Exponential)
CS
• O(2n) or “Order 2n ”: Exponential time
20
o more theoretical rather than practical interest
4 because they cannot reasonably run on typical
computers for even for moderate values of n.
o Input sizes bigger than 40 or 50 become
unmanageable
• Even on faster computers
• O(n!): even worse than exponential!
o Input sizes bigger than 10 will take a long time
15 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Complexity Classes – O(Logarithmic)
CS
• O(n logn):
20 o Only slightly worse than O(n) time
4 • And O(n logn) will be much less than O(n 2)
• This is the running time for the better sorting algorithms
we will go over (later)
• O(log n) or “Order log n”: Logarithmic time
o If input size doubles, running time increases ONLY by
a constant amount
o any algorithm that halves the data remaining to be
processed on each iteration of a loop will be an O(log
n) algorithm.
16 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP
CS
20
4
Algorithm Analysis
Some Example
17 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Algorithm Analysis - Example - 01
CS • The number of operations for (k = 1; k <= n/2; k++) {
20 executed by these loops is sum = sum + 5;
the sum of the individual }
4 loop operations. for (j = 1; j <= n*n; j++) {
• The first loop has n/2 delta = delta + 1;
}
operations
• The second loop has n2
operations In Big-O terms, we can
• Not nested, So we simply
ADD their operations express the number of
• The total number of operations as O(n2)
operations would be
o T(n) = n/2 + n2
18 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Algorithm Analysis - Example - 02
CS • The outer loop runs n int func1(int n) {
20 times int i, j, x = 0;
for (i = 1; i <= n; i++) {
4 • for each of those n for (j = 1; j <= n; j++) {
x++;
times, the inner loop }
also runs n times }
• So we have n operations return x;
}
per iteration of OUTER
loop
• Finally, we have the In Big-O terms, we can express
number of operations the number of operations as
o T(n) = n*n O(n 2
)
19 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Algorithm Analysis - Example - 03
CS
• The loops are NOT int func3(int n) {
20 nested int i, x = 0;
4 • First loop runs n i++)
for (i = 1; i <= n;
x++;
times for (i = 1; i<=n; i+
+)
• Second loop runs n x++;
times }
return x;
• Total runtime is on In Big-O terms, we can express
the order of the number of operations as
o T(n) = n+n = 2n O(n)
20 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Algorithm Analysis - Example - 04
CS • Initially n int func4(int n) {
20 • After first iteration
while (n > 0) {
printf(“%d”, n%2);
4 o n/2 n = n/2;
• After 2nd iteration }
o n/4 }
• After 3rd iteration
o n/8
• After “k” iteration In Big-O terms, we can express
o n/2k the number of operations as
• Algorithm ends when O(log2 n)
o n/2k = 1
• So k = log2 n
21 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Algorithm Analysis - Example - 05
CS int func5(int[][] array, int n) {
int i = 0, j = 0;
20 while (i < n) {
while (j < n && array[i][j] == 1)
4 i++;
j++;
}
return j;
}
• Outer loop can never run more than n times
• Inner loop can never run more than n times
• The MOST number of times these two statements can run
(combined) is 2n times
• we approximate the running time as O(n)
22 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Algorithm Analysis - Example - 06
CS int func6(int[][] array, int n) {
int i = 0, j;
20 while (i < n) {
j = 0;
4
while (j < n && array[i][j] == 1)
j++;
i++;
}
return j;
}
• Outer loop will run n times
• Each outer iteration, Inner loop will run n times
• The MOST number of times these two statements can run n*n
times
• we approximate the running time as O(n2)
23 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Algorithm Analysis - Example - 07
CS int func7(int A[], int sizeA, int B[], int sizeB) {
int i, j;
20 for (i = 0; i < sizeA; i++)
for (j = 0; j < sizeB; j++)
4 if (A[i] == B[j])
return 1;
return 0;
}
• the runtime here is NOT in terms of n
• The outer loop runs sizeA times
• For each iteration of outer loop, the inner loop runs sizeB times
• So this algorithm runs sizeA*sizeB times
• We approximate the running time as O(sizeA*sizeB)
24 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Algorithm Analysis - Example - 08
CS int func8(int A[], int sizeA, int B[], int sizeB) {
int i, j;
20 for (i = 0; i < sizeA; i++) {
if (binSearch(B, sizeB, A[i]))
4 return 1;
}
return 0;
}
• the runtime here is NOT in terms of n
• The outer loop runs sizeA times
• For each iteration of outer loop, the inner loop runs lg(sizeB) times
• So this algorithm runs sizeA*lg (sizeB) times
• We approximate the running time as O(sizeA*lg(sizeB))
25 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP
CS
20
4
Algorithm Analysis
Practical Problems
26 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Big–Oh – Introduction (formal definition)
CS
g n f n : there exist positive constants c and no such that
20
0 f n cg n for all n n o
4
• c * g(n) is an upper
bound on the value of
f(n)
• Such that
• f(n) <= c * g(n)
27 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Practical Problems – Example 01
CS
• An algorithm A runs • T(n) = O (n)
20
in O(n) time o T(n) = c * n
4
• For input size of 10, • n = 10, T(10) = 2ms
the algorithm takes o T(10) = c * 10
2 milliseconds o 2 = c * 10
o c = 1/5
• How much time it
• c = 1/5, n = 500, T(500)=?
will take for input o T(500) = (1/5) * 500
size of 500? o T(500) = 100 ms
28 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Practical Problems – Example 02
CS
• An algorithm A runs • T(n) = O (n2)
20
in O(n2) time o T(n) = c * n2
4
• For input size of 4, • n = 4, T(4) = 10ms
the algorithm takes o T(4) = c * 42
10 milliseconds o 10 = c * 16
o c = 10/16
• How much time it
• c = 10/16, n = 16, T(16)=?
will take for input o T(16) = (10/16) * 162
size of 16? o T(500) = 160 ms
29 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP Practical Problems – Example 03
CS
• An algorithm A runs • T(n) = O (log2n)
20
in O(log2n) time o T(n) = c * log2n
4
• For input size of 16, • n o= 16, T(16) = 28ms
T(16) = c * log216
the algorithm takes o 28 = c * 4
28 milliseconds oc = 7
• How much time it • c = 7, n = 64, T(64)=?
will take for input o T(64) = 7* log264
o T(64) = 7 * 6
size of 64? o T(64) = 42 ms
30 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
Data Structures - I
“No Bonus” marks for this course anymore
CP
CS
20
4
Allah (Alone) is Sufficient for us,
and He is the Best Disposer of
affairs (for us).(Quran 3 : 173)
31 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
