MODULE 1

ALGORITHM ANALYSIS

Chapter 1 @Dr. Ganesh Khekare 1

 Data Structures and Algorithm

A data structure is a particular way of organizing data in a computer so

that it can be used effectively.
For example, we can store a list of items having the same data-type
using the array data structure.

Chapter 1 @Dr. Ganesh Khekare 2

 Importance of Data Structures

As applications are getting complex and data rich, there are three common
problems that applications face now-a-days.
•Data Search − Consider an inventory of 1 million(106) items of a store. If
the application is to search an item, it has to search an item in 1 million(106)
items every time slowing down the search. As data grows, search will
become slower.
•Processor speed − Processor speed although being very high, falls limited
if the data grows to billion records.
•Multiple requests − As thousands of users can search data simultaneously
on a web server, even the fast server fails while searching the data.

To solve the above-mentioned problems, data structures come to rescue.

Data can be organized in a data structure in such a way that all items may
not be required to be searched, and the required data can be searched almost
instantly. Chapter 1 @Dr. Ganesh Khekare 3
 Data Structures

Primitive DS Non-Primitive DS

Int

float Linear( Sequential) Non Linear

(Random)
char

Double
Pointer Arrays List Stack Queue Trees Graph

Single LL Double LL Circular LL Binary Binary

Tree Search Tree
4 Chapter 1 @Dr. Ganesh Khekare
Types of Data Structure
Basically, data structures are divided into two categories:
•Linear data structure
•Non-linear data structure

Linear data structures

In linear data structures, the elements are arranged in sequence one
after the other. Since elements are arranged in particular order, they
are easy to implement.

List of data structure in a linear type of data structure

1. Array
2. Linked list
3. Stack
4. Queue

Chapter 1 @Dr. Ganesh Khekare 5

Non-linear data structure

•A non-linear data structure is another important type in which

data elements are not arranged sequentially; mainly, data
elements are arranged in random order without forming a linear
structure.

• Map
• Graph
• Tree

Chapter 1 @Dr. Ganesh Khekare 6

 Algorithm

n Definition
An algorithm is a finite set of instructions that
accomplishes a particular task.
n Criteria
– input
– output
– definiteness: clear and unambiguous
– finiteness: terminate after a finite number of steps
– effectiveness: instruction is basic enough to be carried
out
Chapter 1 @Dr. Ganesh Khekare 7
An Algorithm Development Process
• How to design Algorithm
1. Divide and Conquer Approach
2. Greedy Technique
3. Dynamic Programming
4. Branch and Bound
5. Backtracking Algorithm etc

• How to validate Algorithm

• How to analyse Algorithm

Space Complexity: The space complexity can be understood as the
amount of space required by an algorithm to run to completion.

Time Complexity: Time complexity is a function of input size n that

refers to the amount of time needed by an algorithm to run to completion.

Chapter 1 @Dr. Ganesh Khekare 8

What is Recursion?

The process in which a function calls itself directly or indirectly is called

recursion and the corresponding function is called a recursive function.

Using a recursive algorithm, certain problems can be solved quite easily.

Examples of such problems are
Towers of Hanoi (TOH)
Inorder/Preorder/Postorder Tree Traversals,
DFS of Graph, etc.

Chapter 1 @Dr. Ganesh Khekare 9

Tower of Hanoi

Chapter 1 @Dr. Ganesh Khekare 10

Chapter 1 @Dr. Ganesh Khekare 11
Chapter 1 @Dr. Ganesh Khekare 12
Chapter 1 @Dr. Ganesh Khekare 13
Advantages of an Algorithm

•Effective Communication: Since it is written in a natural language like

English, it becomes easy to understand the step-by-step delineation of a
solution to any particular problem.
•Easy Debugging: A well-designed algorithm facilitates easy debugging to
detect the logical errors that occurred inside the program.
•Easy and Efficient Coding: An algorithm is nothing but a blueprint of a
program that helps develop a program.
•Independent of Programming Language: Since it is a language-
independent, it can be easily coded by incorporating any high-level
language.

Disadvantages of an Algorithm
•Developing algorithms for complex problems would be time-consuming
and difficult to understand.
•It is a challenging task to understand complex logic through algorithms.

Chapter 1 @Dr. Ganesh Khekare 14

•Time Factor − Time is measured by counting the number of
key operations such as comparisons in the sorting algorithm.

•Space Factor − Space is measured by counting the

maximum memory space required by the algorithm.

The complexity of an algorithm f(n) gives the running time

and/or the storage space required by the algorithm in terms
of n as the size of input data.
Chapter 1 @Dr. Ganesh Khekare 15
 Measurements

n Criteria
– Is it correct?
– Is it readable?
– …
n Performance Analysis (machine independent)
– space complexity: storage requirement
– time complexity: computing time
n Performance Measurement (machine dependent)

Chapter 1 @Dr. Ganesh Khekare 16

 Space Complexity
S(P)=C+SP(I)
Fixed Space Requirements (C)
Independent of the characteristics of the inputs and outputs
– instruction space
– space for simple variables, fixed-size structured variable, constants
– A fixed part that is a space required to store certain data and variables,
that are independent of the size of the problem. For example, simple
variables and constants used, program size, etc.
Variable Space Requirements (SP(I))
depend on the instance characteristic I
– number, size, values of inputs and outputs associated with I
– recursive stack space, formal parameters, local variables, return
address
– A variable part is a space required by variables, whose size depends
on the size of the problem. For example, dynamic memory allocation,
recursion stack space, etc.1 @Dr. Ganesh Khekare
Chapter 17
Algorithm:
SUM(A, B)
Step 1 - START
Step 2 - C ← A + B + 10
Step 3 - Stop

Here we have three variables A, B, and C and one constant. Hence

S(P) = 1 + 3. Now, space depends on data types of given variables
and constant types and it will be multiplied accordingly.

So if A, B, C are declared as 16 bits fixed integers they each will

require 2 Bytes of Memory, so total space required in above
algorithm will become 8 Bytes.

Chapter 1 @Dr. Ganesh Khekare 18

 Time Complexity
T(P)=C+TP(I)
n Compile time (C)
independent of instance characteristics
n run (execution) time TP
n Definition
A program step is a syntactically or semantically
meaningful program segment whose execution
time is independent of the instance characteristics.

Chapter 1 @Dr. Ganesh Khekare 19

Generally, we make three types of analysis to calculate algorithm efficiency, which is
as follows:

Worst-case time complexity: Big-O Notation: Mostly used: For 'n' input size, the
worst-case time complexity can be defined as the maximum amount of time needed by
an algorithm to complete its execution. Thus, it is nothing but a function defined by the
maximum number of steps performed on an instance having an input size of n.

Average case time complexity: Big Theta Notation: Rarely used: For 'n' input size,
the average-case time complexity can be defined as the average amount of time needed
by an algorithm to complete its execution. Thus, it is nothing but a function defined by
the average number of steps performed on an instance having an input size of n.

Best case time complexity: Big Omega Notation: Very Rarely used: For 'n' input
size, the best-case time complexity can be defined as the minimum amount of time
needed by an algorithm to complete its execution. Thus, it is nothing but a function
defined by the minimum number of steps performed on an instance having an input
size of n.

•How to test
❖ Debugging
❖ Profiling
Chapter 1 @Dr. Ganesh Khekare 20
Chapter 1 @Dr. Ganesh Khekare 21
Relations Between Different Sets
Subset relations between order-of-growth sets.
R→R
O( f ) ( f )
•f
( f )

Chapter 1 @Dr. Ganesh Khekare 22

Order Notation
n BIG-O T(n) = O(f(n))
– Upper bound
– Exist constants c and n0 such that
T(n)  c f(n) for all n  n0
n OMEGA T(n) =  (f(n))
– Lower bound
– Exist constants c and n0 such that
T(n)  c f(n) for all n  n0
n THETA T(n) = θ (f(n))
– Tight bound
– θ(n) = O(n) =  (n)

Chapter 1 @Dr. Ganesh Khekare 23

Chapter 1 @Dr. Ganesh Khekare 24
 Asymptotic Notation (O)

n Definition
f(n) = O(g(n)) iff there exist positive constants c
and n0 such that f(n)  cg(n) for all n, n  n0.
n Examples
– Show: 3n+2=O(n) /* 3n+24n for n2 */
– Show: 3n+3=O(n) /* 3n+34n for n3 */
– Show: 100n+6=O(n) /* 100n+6101n for n10 */
– Show: 10n2+4n+2=O(n2) /* 10n2+4n+211n2 for n5 */
– Show: 6*2n+n2=O(2n) /* 6*2n+n2 7*2n for n4 */
Chapter 1 @Dr. Ganesh Khekare 25
Show 3n+2=O(n)

Solution:
We need to find c and n0 such that:
3n+2 <= cn for all n >= n0 .

Divide both sides by n, getting:

3 + 2/n <= c for all n >= n0 .

If we choose n0 equal to 2, then we need a value of c such that:

3 + 1 <= c
4 <= c

We can set c equal to 4. Now we have:

3n + 2 <= 4n for all n >= 2 .

Chapter 1 @Dr. Ganesh Khekare 26

Show 3n2 + 4n - 2 = O(n2).

Solution:
We need to find c and n0 such that:
3n2 + 4n - 2 <= cn2 for all n >= n0 .

Divide both sides by n2, getting:

3 + 4/n - 2/n2 <= c for all n >= n0 .

If we choose n0 equal to 1, then we need a value of c such that:

3 + 4 - 2 <= c
5 <= c

We can set c equal to 5. Now we have:

3n2 + 4n - 2 <= 5n2 for all n >= 1 .

Chapter 1 @Dr. Ganesh Khekare 27

Chapter 1 @Dr. Ganesh Khekare 28
– 3n+2=Omega(n) /* 3n+2>=3n for n1 */
– 100n+6=Omega(n) /* 100n+6>=100n for n1*/
– 10n2+4n+2=Omega(n2) /* 10n2+4n+2>=n2 for n1 */
– 6*2n+n2=Omega(2n) /* 6*2n+n2 >=2n for n1 */

Chapter 1 @Dr. Ganesh Khekare 29

Chapter 1 @Dr. Ganesh Khekare 30
Chapter 1 @Dr. Ganesh Khekare 31
Big O Notation : Time Complexity Details
O(1): Constant Time Complexity O(1) occurs when the program doesn’t contain any
loops, recursive functions or call to any other functions. The run time, in this case,
won’t change no matter what the input value is. (e.g. addition of two numbers
program)

O(n) : Linear Time Complexity O(n) occurs when the run time of the code increases at
an order of magnitude proportional to n. Here n is the size of the input. (e.g loop)

O(log n): Logarithmic Time Complexity O(log n) occurs when at each subsequent step
in the algorithm, the time is decreased at a magnitude inversely proportional to N. This
generally happens in Binary Search Algorithm.

O(n log n): Linearithmic Time Complexity. One example of an algorithm that runs with
this time complexity is Quick Sort, Heap Sort, Merge Sort

O(n²): Quadratic Time Complexity

O(2^n): Exponential Time Complexity

O(n!): Factorial Time Complexity

Chapter 1 @Dr. Ganesh Khekare 32
Following is a list of some common asymptotic notations

Chapter 1 @Dr. Ganesh Khekare 33

Commonly used Rate/Order of
Growths

Chapter 1 @Dr. Ganesh Khekare 34

n log2n nlog2n n^2 2^n

1 0 0 1 2

2 1 2 4 4

4 2 8 16 16

8 3 24 64 256

16 4 64 256 65536

32 5 160 1024 4294967296

Chapter 1 @Dr. Ganesh Khekare 35

Chapter 1 @Dr. Ganesh Khekare 36
Chapter 1 @Dr. Ganesh Khekare 37
Algorithm Best Case Average Case Worst Case
Complexity Complexity Complexity

Insertion Sort Ω(n) Θ(n²) O(n²)

Selection Sort Ω (n²) Θ(n²) O(n²)

Bubble Sort Ω(n) Θ(n²) O(n²)

Merge Sort Ω(n Log(n)) Θ (n Log(n)) O(n Log(n))

Quick Sort Ω(n Log(n)) Θ (n Log(n)) O(n²)

Heap Sort Ω(n Log(n)) Θ (n Log(n)) O(n Log(n))

Radix Sort Ω (nk) Θ (nk) O(nk)

Chapter 1 @Dr. Ganesh Khekare 38