Data structure and algorithm

Department of
Software Engineering
2nd year
Data structure and
Algorithms
Presented by: Demeke M.
Data structure and algorithm

Chapter two
Complexity analysis

Presented by: Demeke M.

 CH 2: Complexity analysis
3
Introduction
 The study of algorithms includes:
• How to Design algorithms (Describing algorithms)
• How to Analyze algorithms (In terms of time and memory space)
• How to validate algorithms (for any input)
• How to express algorithms (Using programming language)
• How to test a program (debugging and maintaining)
But, in this course more focus will be given to Design and Analysis of algorithms.
 CH 2: Complexity analysis
4
Algorithm analysis
o Algorithm analysis refers to the process of determining how much computing
time and storage that algorithms will require.
o In other words, it’s a process of predicting the resource requirement of
algorithms in a given environment.
o In order to solve a problem, there are many possible algorithms. One has to be
able to choose the best algorithm for the problem at hand using some scientific
method.
o To classify some data structures and algorithms as good:
• We need precise ways of analyzing them in terms of resource requirement.
 CH 2: Complexity analysis
5
Cont...
o The main resources are:
• Running Time
• Memory Usage
Note: Running time is the most important since computational time is the most
precious resource in most problem domains.
 CH 2: Complexity analysis
6
How to measure Efficiency?
o There are two approaches to measure the efficiency of algorithms.
1. Empirical
• based on the total running time of the program.
• Uses actual system clock time.
Example:
t1
for(int i=0; i<=10; i++)
cout<<i;
t2
• Running time taken by the above algorithm (Total Time) = t2-t1;
 CH 2: Complexity analysis
7
Cont...
o It is difficult to determine efficiency of algorithms using this approach,
Because clock-time can vary based on many factors.
o For example,
1. Processor speed of the computer
2. Operating system
3. Current processor load
 CH 2: Complexity analysis
8
Cont...
2. Theoretical
o Determining the quantity of resources required using mathematical concept.
o Analyze an algorithm according to the number of basic operations (time units)
required, rather than according to an absolute amount of time involved.
o We use theoretical approach to determine the efficiency of algorithm because:
• The number of operation will not vary under different conditions.
• It helps us to have a meaningful measure that permits comparison of
algorithms independent of operating platform.
• It helps to determine the complexity of algorithm.
 CH 2: Complexity analysis
9
Complexity analysis
o Complexity Analysis is the systematic of the cost of computation, measured in
• Time units
• Operations performed, or
• The amount of storage space required.
o The two important ways to characterize the effective of an algorithm are
1. Time Complexity: Determine the approximate number of operations required
to solve a problem of size n.
2. Space Complexity: Determine the approximate memory required to solve a
problem of size n.
• For most algorithms, running time depends on “size” of the input.
• Running time is expressed as T(n) for some function T on input size n.
 CH 2: Complexity analysis
10
Analysis rule
1. We assume an arbitrary time unit.
2. Execution of one of the following operations takes time 1:
• Assignment operation
• Single input/output operation
• Single Boolean operations
• Single arithmetic operations
• Function return
3. Running time of a selection statement (if, switch) is the time for the condition
evaluation + the maximum of the running times for the individual clauses in the
selection.
 CH 2: Complexity analysis
11
Cont...
4. Loop statements
• The running time for the statements inside the loop * number of
iterations + time for setup(1) + time for checking (number of iteration +
1) + time for update (number of iteration)
• The total running time of statements inside a group of nested loops is the
running time of the statements * the product of the sizes of all the loops.
• For nested loops, analyze inside out.
• Always assume that the loop executes the maximum number of iterations
possible.

5. Running time of a function call is 1 for setup + the time for any parameter
calculations + the time required for the execution of the function body.
CH 2: Complexity analysis
12
Example 1
int x; • 1 for the assignment
int sum=0; statement: int sum=0
if(a>b){ • 1 for if condition statement.
sum= a+b; • In if condition two statement executed.
• The first one is two operator which is 2
cout<<sum; unit
} • The second one unit
else{ • Else condition have 1 output statement
cout<<b;
}
T(n) = 1 +1+max(3,1) = 5
 CH 2: Complexity analysis
13
Example 2
int count(){ int k=0; • 1 for the assignment
cout<<“Enter an integer”; statement: int k=0
cin>>n; • 1 for the output statement.
for (i=0;i<n;i++) • 1 for the input statement.
• In the for loop:
k=k+1; – 1 assignment, n+1 tests, and n
return 0; increments.
} – n loops of 2 units for an assignment, and
an addition.
T(n) = 1+1+1+(1+(n+1)+n)+2n+1)= 4n+6
• 1 for the return statement.
 CH 2: Complexity analysis
14
Example 3
void func(){
int x=0; int i=0; int • 1 –each 3 - assign statement
j=1; • 1– output statement
cout<<“Enter an Integer”; • 1 – input stmt.
cin>>n; • 1st while loop:
while (i<n){
– n+1 tests
x++; i++;
} – n loops of 2 units for the two increment
while (j<n){ j++; (addition) operations
} • 2nd while loop:
} – n tests
– n-1 increments
T (n)= 1+1+1+1+1+n+1+2n+n+n-1 = 5n+5
 CH 2: Complexity analysis
15
Example 4
sum = 0; • 1- assign statement
for (i=1; i<=n; i++) • Inner loop:
for (j=1; j<=n; j++) • 1 assign, n+1 tests, and n increments.
• Loop executes n times
sum=sum+1;
• Outer loop:
• 1 assign, n+1 tests, and n increments.
• Loop executes n times
• Statement inside nested loop:
– 2 units, assign & increment
T(n)= 1+2(1+(n+1)+n)+2n2 = 2n2 +4n+5 – Total: 2 *(n*n) –>size of both loops
CH 2: Complexity analysis
16
Exercise 1
int sum=0; Answer:
if(test=){ T(n) = 1+1+Max(1+n+1+n+n+n,1)
for (int i=1;i<=n;i++) = 4n+4
sum=sum+i;
}
else{
cout<<sum;
}
 CH 2: Complexity analysis
17
Exercise 2
• Calculate T(n) for the following codes
3) int i=0;
1) int sum=0;
while(i<n){
for(i=1; i<=n; i++)
cout<<i;
for(j=1; j<=m; j++) i++;
sum++; }
int j=1;
Answer? while(j<=10){
2) int sum=0; cout<<j;
for(i=1; i<=n; i++) j++;
for(j=1; j<=i; j++) }
sum++; Answer ?

Answer ?
 CH 2: Complexity analysis
18
Formal approach to Analysis
o In the previous examples we have seen that analyzing Loop statements is so
complex.
o It can be simplified by using some formal approach in which case we can
ignore:
• Initializations
• Loop control condition
• Loop counter increments, etc.
o Primary consideration when estimating an algorithm’s performance is the
number of basic operations required by the algorithm to process an input of a
certain size.
 CH 2: Complexity analysis
19
Cont...
o Size: the number of inputs processed.
o Example
• Sorting algorithms, size is the number of records to be sorted.
o A basic operation must have the property that its time to complete does not
depend on the particular values of its operands.
o Example
• Adding or comparing two integer variables.
• Summing the contents of an array containing n integers is not, because the
cost depends on the value of n (i.e. the size of the input).
 CH 2: Complexity analysis
20
Cont...
o For loop
• A for loop translates to a summation.
• The index and bounds of the summation are the same as the index and bounds of the for
loop.

for (int i=1;i<=N; i++){

sum = sum + i;
}

• Suppose we count the number of additions that are done.

• There is 1 addition per iteration of the loop, hence N additions in total.
 CH 2: Complexity analysis
21
Formal approach to Analysis
o Nested loop
• Nested for loops translate into multiple summations, one for each for loop.

• Again, count the number of additions. The outer summation is for the outer for
loop.
 CH 2: Complexity analysis
22
Cont...
o Consecutive statement
• Add the running times of the separate blocks
 CH 2: Complexity analysis
23
Cont...
o Conditional statement
• If (test) s1 else s2: Compute the maximum of the running time for s1 and s2.
 CH 2: Complexity analysis
24
Category of algorithm analysis
o Algorithm may be examined under different situations to correctly determine the
efficiency for accurate comparison.
1. Best case analysis: computes the lower bound of T(n), where T(n) is the
complexity function.
• Assumes the input data are arranged in the most advantageous order for the
algorithm.
• Takes the smallest possible set of inputs.
• Causes execution of the fewest number of statements.
o Example
• For sorting algorithm: If the list is already sorted (data are arranged in the
required order).
• For searching algorithm: If the desired item is located at first accessed position.
 CH 2: Complexity analysis
25
Cont...
2. Worst case analysis
• Assumes the input data are arranged in the most disadvantageous order for the
algorithm.
• Takes the worst possible set of inputs.
• Causes execution of the largest number of statements(operations).
• Computes the upper bound of T(n) where T(n) is the complexity function.
o Example:
• While sorting, if the list is in opposite order. While searching, if the desired item
is located at the last position or is missing.
 CH 2: Complexity analysis
26
Cont...
3. Average case analysis
• Determine the average of the running time overall permutation of input data.
• Takes an average set of inputs.
• It also assumes random input size.
• It causes average number of executions.
• Computes the optimal bound of T(n) where T(n) is the complexity function.
• Sometimes average cases are as bad as worst cases and as good as best cases.
o Example:
• For sorting algorithms: While sorting, considering any arrangement (order of
input data).
• For searching algorithms: While searching, if the desired item is located at any
location or is missing.
 CH 2: Complexity analysis
27
Asymptotic analysis
o Asymptotic Analysis is concerned with how the running time of an algorithm
increases with the size of the input in the limit, as the size of the input increases
without bound!
o How the running time of an algorithm increase when the size of the input
increase?
o Type of Asymptotic Analysis makes use of
1. O (Big-Oh) ,
2.  (Big-Omega),
3.  (Theta),
4. o (little-o) and
5.  (little-omega)
 CH 2: Complexity analysis
28
Big-Oh notation
o Definition: We say f(n)=O(g(n)), if there are positive constants k and c,
such that to the right of k, the value of f(n) always lies on or below
c.g(n).
• As n increases f(n) grows no faster than g(n).
• It’s only concerned with what happens for very large values of n.
• Describes the worst - case analysis.
• Gives an upper bound for a function to within a constant factor.
 CH 2: Complexity analysis
29
Cont...

• O-Notations are used to represent the amount of time an algorithm takes on

the worst possible set of inputs, “Worst-Case”
 CH 2: Complexity analysis
30
Cont...
o Example 1
f(n)=10n+5 and g(n)=n.
Show that f(n) is O(g(n))?
• To show that f(n) is O(g(n)), we must show that there exist constants c
and k such that f(n)<=c.g(n) for all n>=k.
10n+5< = c.n ➔for all n>=k
let c=15, then show that 10n+5<=15n 5<=5n or 1<=n
So, f(n)=10n+5<=15.g(n) for all n>=1
(c=15, k=1), there exist two constants that satisfy the above constraints.
 CH 2: Complexity analysis
31
Cont...
o Example 2
f(n)=3n2+4n+1.
Show that f(n)=O(n2)?
3n2 <=3n 2 for all n>=1
4n<=4n2 for all n>=1 and
1<=n2 for all n>=1
3n2+4n+1<=3n2+4n2+n2 for all n>=1 <=8n 2 for all n>=1

• So, we have shown that f(n)<=8n2 for all n>=1. Therefore, f(n) is
O(n2), (c=8, k=1), there exist two constants that satisfy the constraints.
CH 2: Complexity analysis
32
Exercise
Find Big-Oh of the following algorithm.
1. for( int i=1;i<=n; i++)
sum = sum + i;
Answer = O(n).

2. for(int i=1; i<=n; i++)

for(int j=1; j<=n; j++)
k++;

Answer = O(n2).
CH 2: Complexity analysis
33
Cont...
T(n) Complexity Category Big-O
functions F(n)
c, c is constant 1 C=O(1)
10logn + 5 logn T(n)=O(logn)
√n +2 √n T(n)=O(√n)
5n+3 n T(n)=O(n)
3nlogn+5n+2 nlogn T(n)=O(nlogn)
10n2 +nlogn+1 n2 T(n)=O(n2)
5n3 + 2n2 + 5 n3 T(n)=O(n3)
2n+n5+n+1 2n T(n)=O(2n)
7n!+2n+n2+1 n! T(n)=O(n!)
8nn+2n +n2 +3 nn T(n)=O(nn)
CH 2: Complexity analysis
34
Cont...
 CH 2: Complexity analysis
35
Big-Omega () Notation
o Definition: We write f(n)= (g(n)) if there are positive constants k and
c such that to the right of k the value of f(n) always lies on or above
c.g(n).
• As n increases f(n) grows no slower than g(n).
• Describes the best-case analysis.
• Used to represent the amount of time the algorithm takes on the
smallest possible set of inputs-“Best case”.
CH 2: Complexity analysis
36
Cont...

o It compute lower bound

 CH 2: Complexity analysis
37
Cont...
o Example 1:
Find g(n) such that f(n) = (g(n)) for f(n)=3n+5, g(n) = √n, c=1, k=1.
f(n)=3n+5= (√n)

o Example 2:
Find g(n) such that f(n) = (g(n)) for f(n)=n2
g(n) = n, c=1, k=1.
f(n)=n2=(n)
 CH 2: Complexity analysis
38
Theta () notation
o Definition: We say f(n)= (g(n)) if there exist positive constants no, c1 and
c2 such that to the right of no, the value of f(n) always lies between c1.g(n)
and c2.g(n) inclusive, i.e., c2.g(n)<=f(n)<=c1.g(n), for all n>=n o.
• As n increases f(n) grows as fast as g(n).
• Describes the average case analysis.
• To represent the amount of time the algorithm takes on an average set of
inputs “Average case”.

o Example 1:
Find g(n) such that f(n) = Θ (g(n)) for f(n)=2n2+3
n2 ≤ 2n2 ≤ 3n2
c1=1, c2=3 and no=1
f(n) = Θ(g(n)).
CH 2: Complexity analysis
39
Cont...
 CH 2: Complexity analysis
40
Little-oh (small-oh) Notation
o Definition: We say f(n)=o(g(n)), if there are positive constants no and c such that to
the right of no, the value of f(n) lies below c.g(n).
• As n increases, g(n) grows strictly faster than f(n).
• Describes the worst - case analysis.
• Denotes an upper bound that is not asymptotically tight.
• Big O-Notation denotes an upper bound that may or may not be asymptotically
tight.
Example:
Find g(n) such that f(n) = o(g(n)) for f(n) = n2 n2<2n2, for all n>1, ➔ k=1, c=2,
g(n)=n2 n2< n3, g(n) = n3, f(n)=o(n3)
n 2< n4 , g(n) =n4 , f(n)=o(n4)
 CH 2: Complexity analysis
41
Little-Omega () notation
o Definition: We write f(n)= (g(n)), if there are positive constants no and c such
that to the right of no, the value of f(n) always lies above c.g(n).
• As n increases f(n) grows strictly faster than g(n).
• Describes the best - case analysis.
• Denotes a lower bound that is not asymptotically tight.
• Big -Notation denotes a lower bound that may or may not be asymptotically
tight.
Example: Find g(n) such that f(n)= (g(n)) for f(n)=n2+3
g(n)=n, Since n2 > n, c=1, k=2.
g(n)=√n, Since n2 > √n, c=1, k=2, can also be solution.
Any question !