Design and Analysis of Algorithm

FALL 2024

Lecture No:01(C)
Time Complexity of Algorithm and its
importance

Course Instructor: Ms. AQSA AQDUS

 The RAM Model

 Random Access Machine (not R.A. Memory)

 An idealized notion of how the computer
works
– Each "simple" operation (+, -, =, if) takes exactly
1 step.
– Each memory access takes exactly 1 step
– Loops and method calls are not simple
operations, but depend upon the size of the data
and the contents of the method.
 Measure the run time of an algorithm by
counting the number of steps.
2
 Random Access Machine
 A Random Access Machine (RAM) consists . . .
of: input tape
– a fixed program
– an unbounded memory
– a read-only input tape
Program

...
– a write-only output tape Memory
 Each memory register can hold an
output tape
arbitrary integer (*). . . .
 Each tape cell can hold a single symbol
from a finite alphabet s. Instruction set:
x  y, x  y {+, -, *, div, mod
goto label
if y {<, , =,  ,> , } z goto
x  input, output  y
3 halt
 Space Complexity
 The amount of memory required by an
algorithm to run to completion
– The term memory leaks refer to the
amount of memory required is larger
than the memory available on a given
system

4
 Space Complexity (Cont !!!)

 Fixed part: The size required to store certain

data/variables, that is independent of the size
of the problem:

– Such as int a (2 bytes, float b (4 bytes) etc

 Variable part: Space needed by variables,

whose size is dependent on the size of the
problem:
– Dynamic array a[]

5
 Space Complexity (cont’d)
S(P) = c + S(instance characteristics)
– c = constant
Example:
void float sum (float* a, int n)
{
float s = 0;
for(int i = 0; i<n; i++) {
s+ = a[i];
}
return s;
}
Constant Space:
one for n, one for a [passed by reference!], one for s, one for
i , constant space=c=4
6
 Running Time of Algorithms
 Running time
– depends on input size n
 size of an array
 polynomial degree
# of elements in a matrix
# of bits in the binary representation of the input
 vertices and edges in a graph

– number of primitive operations performed

 Primitive operation
– unit of operation that can be identified in the pseudo-code

7
 Steps To determine Time
Complexity

Step-1. Determine how you will measure input size.

Ex:
– N items in a list
– N x M table (with N rows and M columns)
– Two numbers of length N

Step-2. Choose the type of operation (or perhaps

two operations)
– Comparisons
– Swaps
– Copies
– Additions

Note: Normally we don't count operations in

8
input/output.
 Steps To determine Time
Complexity (Cont !!!)

Step-3. Decide whether you wish to count

operations in the
– Best case? - the fewest possible operations
– Worst case? - the most possible operations
– Average case? This is harder as it is not
always clear what is meant by an "average case".
Normally calculating this case requires some
higher mathematics such as probability theory.
Step-4. For the algorithm and the chosen case
(best, worst, average), express the count as a
function of the input size of the problem.
9
 Steps To determine Time
Complexity (Cont !!!)

5. Given the formula that you have determined,

decide the complexity class of the algorithm.

Q. What is the complexity class of an algorithm?

A. a complexity class is a set of problems of
related resource-based complexity, such as P, NP
classes
Q. Is there really much difference between
3n
5n + 20
and 6n -3
10 A. Yes but when n is large?
 Primitive Operations in an
algorithm

 Assign a value to a variable (i.e. a=5)

 Call a method (i.e. method())
 Arithmetic operation (i.e. a*b, a-b*c)
 Comparing two numbers ( i.e. a<=b,
a>b &&a>c)
 Indexing into an array (i.e. a[0]=5)
 Following an object reference (i.e. Test
obj)
 Returning from a method (i.e. return I )

11
 Assignment Statement

 The running time of a an assignment is

considered as constant
 Examples:
– A=5;
– A[5]=7
– C=a+b;

Note:- Running time of

assignments can be
considered as 1 or C (Refer to
12
constant values)
 for Loops

 The running time of a for loop is at

most the running time of the
statements inside the for loop
(including tests) times the number of
Let
iterations. 1.running time of basic
Example operations is constant
C
For(i=0;i<=n-1;i++)
2.and loop is iterated n
A[i]=0;
Note: times then
(number of basic steps Total Running time will
in loop body) * (number be
13 of iterations) n*c
 Nested for Loops

 The total running time of a statement

inside a group of nested for loops is the
running time of the statement
multiplied by the product ofLet
the sizes of
all the for loops. 1.running time of basic
operations is constant
 Example
C
for(i=0;i<=n-1;i++) 2.Running time of outer
loop (i.e. i) is n
for(j=0;j<=m-1;j++) 3.And running time of
K++; Inner loop (i.e. j) is m
4.Total Running time
14 will be m*n*c
 Consecutives for Loops

 The total running time of consecutive

loops is the sum of running of all
consecutives loops
Let
 Example
1.running time of basic
for(i=0;i<=n-1;i++)operations is constant
C
K++;
2.Running time of loop
for(j=0;j<=m-1;j++)(i.e. i) is n
K++; 3.And running time of
loop (i.e. j) is m
4.Total Running time
15 will be n*c + m * c
 Conditional Statements

 The running time of an if-else statement is

never more than the running time of the
test plus the larger of the running times of
S1 and S2.
Let
 Example 1.Condition is true and
if(Condition) path have one basic
operation (i.e. S1) then
S1; Ruining time will be
else constant C1
2.Similarly, if condition is
Note:S2; false and path have one
Number of basic basic operation (i.e. S2)
16 steps on branch that is then Ruining time will be
 Primitive Operations:
Example -1

 Count the number of primitive operations in

this program : Primitive Yes/ Total
Operations No
Int method()
Assign a value to a
{ variable
i = 0; Call a method
Arithmetic
a = 0; operation
for (i=1;i<=n;i++) Comparing two
numbers
{ printf(“%d”,i);Indexing into an
a=a+i; } array
Following an
return I object reference
} Returning from a
method
17
 Primitive Operations:
Example -1 (Cont !!!)

Primitive Operations Yes/No Total

Assign a value to a Yes 5

variable
Call a method No 0
Arithmetic operation Yes 2
Comparing two numbers Yes 1

Indexing into an array No 0

Following an object No 0
reference
Returning from a method Yes 1
18
 Primitive Operations -
Example 2
 Count the number of primitive operations in
this program :
Primitive Yes/ Total
Int method() Operations No
{ i = 0; Assign a value to a
variable
a = 0;
Call a method
for (i=1;i<=n;i++) Arithmetic
{ printf(“%d”, i); operation

for (a=1;a<=n;a++) Comparing two

numbers
printf(“%d”,a); Indexing into an
} array
Following an
return I object reference
} Returning from a
method
19
 Primitive Operations -
Example 2 (Cont !!!)

Primitive Operations Yes/No Total

Assign a value to a yes 6
variable
Call a method No 0
Arithmetic operation yes 2
Comparing two numbers yes 2
Indexing into an array No 0
Following an object No 0
reference
Returning from a method yes 1
20
 Counting Primitive
Operations

Algorithm ArrayMax(A,n)
{An array A storing N integers
and find the largest element in A.}

currentMax = A[0] 2 steps + 1 to initialize i

for (i=1;i<=n-1;i++)
2 step each time (compare i to n, inc i)
n-1 if (currentMax < A[i])2 steps
time currentMax = A[i] 2 stepsHow often done??
s
return currentMax 1 step

Between 4(n-1) and 6(n-1) in the loop

It depends on the order the numbers appear in in A
21
 Run Time Analysis

 Pseudo code to find product of two numbers

int method()
{ Run Time Complexity
int a,b,c; --------- c1 will be = c1+c2+c2 +
a=2; --------- c2 c3 + c4
b=3; --------- c2 = c1 + 2c2 + c3 + c4
c= a*b; --------- c3
(as all constant)
printf(“Product of a and b is %d”, c);
=C
return 0; ----------- c4
}

22
 Run Time Analysis (Cont !!!)
Run Time Complexity
int method()
will be = c1+c2+c2 + c3
{
int a,b,large; --------- c1
+c2 + c2 + c4
a=2; --------- c2 = c1 + 4c2 + c3 +c4 (as
b=3; --------- c2 all constants)
if(a>b) -------- c3 =C
large=a; -------- c2 Note:- =You can say
else there should be 3c2
large = b; ------- c2 instead of 4c2
printf(“Large number is %d”, large);
(Coefficient have no
Return 0; ---------- c4 impact)
}
23
 Run Time Analysis (Cont !!!)
int method()
{
int I, codd, ceven, a[5]={5,4,3,2,1}; --------- c1
ceven=0;codd=0; ----------- c2
Run Time Complexity
for(i=0;i<=4;i++) ------ c3
if(a[i]%2==0) -------- c4
will be = c1+c2 + n*
ceven++;-------- c5 (c3 +c4 + c5)+ c6
else = c1 + c2 + n*c +c6
codd++; ------- c5 = n*c + c
= nOdd %d”, ceven,
printf(“Total evens %d and Total
codd);
Return 0; ---------- c6
}
24
 Run Time Analysis (Cont !!!)

int method()
{ Run Time Complexity
int I, a[5]; --------- c1 will be = c1 + n * c2 +
for(i=0;i<=4;i++) ------n*(c1+c3)
c2 + n * c2 +
Scanf(“%d”, &a[i]); c4
for(i=0;i<=4;i++) = c1 + 2n*c2 + n * c
A[i]=a[i]+5; -----------=c3c1 + n * c + n * c
for(i=0;i<=4;i++) = 2n*c +c1
print(“%d”, a[i]); = 2n
return 0; ---------- c4 =n
}
25
 Types of Algorithm
Complexity

 Worst Case Complexity:

– the function defined by the maximum number
of steps taken on any instance of size n
 Best Case Complexity:
– the function defined by the minimum number
of steps taken on any instance of size n
 Average Case Complexity:
– the function defined by the average number of
steps taken on any instance of size n

26
 Types of Algorithm Complexity
(Example: Linear Search)
5 7 2 6 9 12 1
 Worst Case Complexity:
– You want to search 1 in above array which is at location
N
– You need N steps
 Best Case Complexity:
– You want to search 5 in above array which is at location
1
– You need 1 steps
 Average Case Complexity:
– You want to search 2 or 9 etc in above array
27 – You need 3 steps for 2 and 5 steps for 9
 Best, Worst, and Average
Case Complexity

Numb Worst Case

er of Complexity
steps

Average Case
Complexity

Best Case
Complexity

N
(input
size)
28
 Relationship between
complexity types and running
time of Algorithms
 Worst case
– Provides an upper bound on running time
– An absolute guarantee that the algorithm would not run
longer, no matter what the inputs are
 Best case
– Provides a lower bound on running time
– Input is the one for which the algorithm runs the fastest

Lower Bound Running Time Upper Bound

 Average case
– Provides a prediction about the running time
29
– Assumes that the input is random
 Running Time
 Most algorithms transform
input objects into output best case
objects. average case
 The running time of an 120
worst case

algorithm typically grows

with the input size. 100

Running Time
 Average case time is often 80

difficult to determine. 60
 We focus on the worst 40
case running time.
20
– Easier to analyze
0
– Crucial to applications 1000 2000 3000 4000
such as games, finance Input Size
and robotics
30
 Summary

 RAM model is used to measure the run

time of an algorithm by counting the
number of steps.
 Space complexity of an algorithm refer to
the amount of memory required to run.
 Time complexity of an algorithm refer to
its running time, which depends on input
size.
 Primitive operations refer to the unit of
operation that can be identified in the
31 pseudo-code.