Lecture Title: Analysis of Algorithms

Course Code: CSC 2211 Course Title: Algorithms

Dept. of Computer Science

Faculty of Science and Technology

Lecture No: 01 Week No: 01 Semester: Summer 22-23

Lecturer: Pritam Khan Boni, [email protected]
Analysis of Algorithms

 Efficiency:
 Running time
 Space used

 Efficiency as a function of the input size:

 Number of data elements (numbers, points).
 The number of bits of an input number .
The RAM Model
 RAM model represents a “generic” implementation of the
algorithm
 Each “simple” operation (+, -, =, if, call) takes exactly 1 step.
 Loops and subroutine calls are not simple operations, but
depend upon the size of the data and the contents of a
subroutine. We do not want “sort” to be a single step
operation.
 Each memory access takes exactly 1 step.
The RAM model (cntd..)

 It is important to choose the level of detail.

 The RAM model:

 Instructions (each taking constant time), we usually choose one type of
instruction as a characteristic operation that is counted:
 Arithmetic (add, subtract, multiply, etc.)
 Data movement (assign)
 Control flow (branch, subroutine call, return)
 Comparison (logical ops)
 Data types – integers, characters, and floats
Time complexity familiar tasks
Task Growth rate
Matrix/vector multiply O(N2)
Getting a specific element from a list O(1)
Dividing a list in half, dividing one halve in half, etc O(log2N)
Binary Search O(log2N)
Scanning (brute force search) a list O(N)
Nested for loops (k levels) O(Nk)
Merge Sort O(N log2N)
Bubble Sort
O(N2)
Generate all subsets of a set of data
O(2N)
Generate all permutations of a set of data
O(N!)
Performance Analysis

 Performance often draws the line between what is feasible and what is impossible.

 Often it is sufficient to count the number of iterations of the core (innermost) part.
 No distinction between comparisons, assignments, etc (that means roughly the same cost for all of
them).
 Gives precise enough results.

 In some cases, the cost of selected operations dominates all other costs.
 Disk I/O versus RAM operations.
 Database systems.
Best/ Worst/ Average Case
 Best case: works fast on some input.

 Worst case: (usually) maximum time of algorithm on any input of size.

 Average case: (sometimes) expected time of algorithm over all inputs of size. Need
assumption of statistical distribution of inputs.

 Analyzing insertion sort’s

 Best case: elements already sorted, tj=1, running time » (n-1), i.e., linear time.
 Worst case: elements are sorted in inverse order, tj = j-1, running time » (n2-n)/2 , i.e.,
quadratic time.
 Average case: tj = j / 2, running time » (n2+n-2)/4 , i.e., quadratic time.
Best/ Worst/ Average Case
 For inputs of all sizes:

worst-case

6n average-case
Running time

5n
best-case
4n

3n

2n

1n

1 2 3 4 5 6 7 8 9 10 11 12 …..
Input instance size
Best/ Worst/ Average Case
 Worst case is usually used:

 It is an upper-bound.

 In certain application domains (e.g., air traffic control, surgery) knowing the worst-case
time complexity is of crucial importance.
 For some algorithms worst case occurs fairly often

 The average case is often as bad as the worst case.

 Finding the average case can be very difficult.

Asymptotic Notation

 Asymptotic Notations are languages that allow us to analyze an algorithm's running

time by identifying its behavior as the input size for the algorithm increases.

 This is also known as an algorithm's growth rate.(Wiki)

Asymptotic Notation
 The “big-Oh” O-Notation
 asymptotic upper bound

 f(n) = O(g(n)), if there exists constants c>0 and n0>0, s.t. f(n) £ c g(n) for n ³ n0
 f(n) and g(n) are functions
c  g (n)
over non- negative integers f (n )

Running Time
 Used for worst-case analysis

n0 Input Size
Asymptotic Notation
Asymptotic Notation
 The “big-Omega” W-Notation
 asymptotic lower bound

 f(n) = W(g(n)) if there exists constants c>0 and n0>0, s.t. c g(n) £ f(n) for n ³ n0

 Used to describe best-case running times or lower bounds of algorithmic problems.

E.g., lower-bound of searching in an unsorted array is W(n). f (n )

Running Time
c  g (n)

n0 Input Size
Asymptotic Notation
 The “big-Theta” Q-Notation
 asymptoticly tight bound

 f(n) = Q(g(n)) if there exists constants c1>0, c2>0, and n0>0, s.t. for n ³ n0 c1 g(n) £ f(n) £ c2 g(n)

 f(n) = Q(g(n)) if and only if f(n) = O(g(n)), f(n) = W(g(n)) c 2  g (n )

f (n )

Running Time
c 1  g (n )
 O(f(n)) is often abused instead of Q(f(n))

n0 Input Size
Asymptotic Analysis

 Goal: to simplify the analysis of the running time by getting rid of details, which are
affected by specific implementation and hardware
 rounding of numbers: 1,000,001 » 1,000,000
 rounding of functions: 3n2 » n2

 Capturing the essence: how the running time of an algorithm increases with the size
of the input in the limit.
 Asymptotically more efficient algorithms are best for all but small inputs
Asymptotic Analysis
 Simple Rule: Drop lower order terms and constant factors.
 50 n log n is O(n log n)
 7n - 3 is O(n)
 8n2 log n + 5n2 + n is O(n2 log n)

 Note: Although (50 n log n) is O(n5), it is expected that an approximation is of the

smallest possible order.
Correctness of Algorithms

 An algorithm is correct if for any legal input it terminates and produces the desired
output.

 Automatic proof of correctness is not possible (so far).

 There are practical techniques and rigorous formalisms that help to reason about the
correctness of (parts of) algorithms.
Partial and Total Correctness
 Partial correctness
IF this point is reached, THEN this is the desired output

Any legal input Algorithm Output

 Total correctness
INDEED this point is reached, AND this is the desired output

Any legal input Algorithm Output

Assertions

 To prove partial correctness, we associate several assertions (statements about the state of the

execution) with specific checkpoints in the algorithm.

 E.g., A[1], …, A[ j ] form an increasing sequence

 Preconditions – assertions that must be valid before the execution of an algorithm or a

subroutine (INPUT).

 Postconditions – assertions that must be valid after the execution of an algorithm or a

subroutine (OUTPUT).
Loop invariants
 Loop Invariant: is a property of a program loop that is true before (and after) each
iteration.
 Initialization: It is true prior to the first iteration of the loop.

 Maintenance: If it is true before an iteration of the loop, it remains true before the
next iteration.
 Termination: When the loop terminates, the invariant gives us a useful property that
helps show that the algorithm is correct.
Growth Rates and Dominance Relations
Proof by Induction

 We want to show that property P is true for all integers n ³ n0.

 Basis: prove that P is true for n0.

 Inductive step: prove that if P is true for all k such that n0 £ k £ n – 1

then P is also true for n.
 Example n
n( n  1)
S ( n)  i 
i 0 2
for n  1
1
1(1  1)
S (1)   i 
 Basis i 0 2
Proof by Induction
 Inductive Step k
k (k  1)
S (k )   i  for 1  k  n  1
i 0 2
n n 1
S (n)   i  i  n S (n  1)  n 
i 0 i 0

(n  1  1) ( n 2  n  2n)
 (n  1) n 
2 2
n(n  1)

2