Analysis of Algorithms (CA 419)
Module I
An Introduction to Computer Algorithms
What is an Algorithm?
An “algorithm” is a finite sequence of well-defined instructions which converts a set of values,
called ‘input’ to a set of values called ‘output’. These well-defined steps should be completed
within finite amount of time.
Algorithm – 1) Design
2) Analysis
Designing of an Algorithm:
Methodology
Correctness of an Algorithm
• Algorithm should terminate after finite number of steps
• Algorithm would generate correct answer for each input
instance
Analyzing an Algorithm:
Efficiency of an algorithm is measured by the amount of resources it
requires. Analyzing an algorithm is to predict the amount of resources it
requires.
Resource: memory, time, communication bandwidth, etc.
Execution time of an Algorithm:
Model of Computation
Problem Size
Number of instructions executed by the algorithm
Model of Computation
Generic Random Access Machine (RAM)
Executes operations sequentially
Set of primitive operations:
Arithmetic, Logical, Comparisons, Function calls
Simplifying assumption: all ops cost 1 unit
Eliminates dependence on the speed of computer,
otherwise impossible to compare
Problem Size
The running time depends on the input: an already sorted sequence may be easier to
sort.
Major Simplifying Convention:
Parameterize the running time by the size of the input (short sequences are
easier to sort than long ones).
TA(n) = time of A on length n inputs
Generally, we seek upper bounds on the running time, to have a guarantee of
performance.
Running time of an Algorithm
Running time of an algorithm on a particular input is the number of primitive
operations / instructions executed by the algorithm
Primitive/basic operations: addition, subtraction, multiplication, division,
comparison, swap, etc.
Running time of an algorithm depends on input instances
Best case
Worst case
Average case
Worst-case:
• T(n) = maximum time of algorithm on any input of size n.
Average-case:
• T(n) = expected time of algorithm over all inputs of size n.
• Needs an idea of statistical distribution of inputs.
Best-case:
• Cheating with a slow algorithm that works fast on some input.
Examples: Sorting Algorithms:
1. Bubble Sort
2. Selection Sort
3. Insertion Sort
Algorithm Bubble Sort (A, n)
for i ← 1 to n-1
(Bubble up the largest element in A[1 . . n-i+1] in A[ n-i+1])
for j ← 1 to n – i do
if (A[j] > A[j+1) then
swap (A[j] A[j+1])
Bubble sort – sorts the elements in place
Algorithm Selection Sort (A, n)
for i ← 1 to n-1
(Select the largest element in A[1 . . . n-i+1] and swap it with A[ n-i+1])
max = A[i]
for j ← 1 to n – i +1 do
if (A[j] > max) then
max ← A[j]
position ← j
end if
end for
A[position] ← A[n-i+1]
A[n-i+1] ← max
end for
Selection sort – sorts the elements in place
Algorithm INSERTION-SORT (A, n)
for j ← 2 to n do
key ← A[ j ]
(Insert A[ j ] in the right position of the sorted sequence A[1 . . j -1])
i←j-1
while (i > 0 and A[i] > key) do
A[i + 1] ← A[i]
i←i–1
A[i + 1] ← key
Insertion sort – sorts the elements in place
Sorting Algorithms Best Case Worst Case
Bubble Sort O(n2) O(n2)
Selection Sort O(n2) O(n2)
Insertion Sort O(n) O(n2)
Example 4
Problem: Compute xn
Inputs: x, n
Output: xn
(A) Naive Approach:
prod ← x
for i ← 1 to (n-1)
prod ← prod * x
output prod
T(n) = O(n)
(B) Better Approach
Let n = (bk-1 bk-2 bk-3 ….. b2 b1 b0)2
Algorithm Power (x, n)
prod ← 1
y←x
for i ← 0 to ⌊𝒍𝒐𝒈 𝒏⌋ do
if (𝑏 ≠ 0) then
prod ← prod * y
end if
y←y*y
end for
return prod
𝑇(𝑛) = ⌈log 𝑛⌉ + 𝛾
Where, 𝛾 is the number of non-zero bits in the binary representation of n
𝛾 can be 0, 1, 2, …, ⌈log 𝑛⌉
Best Case: Worst Case:
𝑇 (𝑛) = ⌈log 𝑛⌉ 𝑇 (𝑛) = 2⌈log 𝑛⌉
Average Case:
Let, n = (bk-1 bk-2 bk-3 ….. b2 b1 b0)2 and k = ⌈log 𝑛⌉
There are 2k possible sequences of length k. We are to find for all such scenarios
what the average number of comparisons is.
If i be the number of non-zero bits in the binary representation of n, then
𝑇(𝑛) = ⌈log 𝑛⌉ + 𝑖 = k + i
Now, there are kCi such sequences among 2k possible sequences. Hence,
1 𝑘 (𝑘
𝑇 (𝑛) = + 𝑖)
2 𝑖
𝑘 𝑘 (𝑖)
𝑇 (𝑛) = [𝑘∑ + ∑ ]
𝑖 𝑖
𝑘−1
𝑇 (𝑛) = [𝑘 2 + 𝑘 ∑ ]
𝑖
⌈ ⌉
𝑇 (𝑛) = [𝑘 2 + 𝑘2 ]= =
References:
1. T. H. Cormen, C. E. Leiserson and R. L. Rivest. Introduction to Algorithms
2. A. V. Aho, J. E. Hopcroft and J. D. Ullman. The Design and Analysis of Computer
Algorithms.
3. E. Horowitz, S. Sahni and S. Rajasekaran. Fundamentals of Computer algorithms.
4. D. E. Knuth. Fundamental Algorithms, Vol. 1 The Art of Computer Programming
5. D. E. Knuth. Sorting and Searching, Vol. 3 The Art of Computer Programming
6. http://www.cs.ucf.edu/~dmarino/ucf/cop3503/lectures/
