The ICFAI University Jaipur

Design and Analysis of Algorithm

First Semester: 2025–2026

1. Introduction Design and Analysis of Algorithm:

Design and Analysis of Algorithms is a foundational subject in computer science that focuses
on developing efficient step-by-step procedures (algorithms) to solve computational problems
and analyzing their performance in terms of time and space complexity.
1.1 What is Design (in Algorithms)?
Design is the process of creating an algorithm to solve a specific problem.
It involves thinking logically, choosing the right strategy, and developing a step-by-step solution.
Common Design Strategies:

Strategy Description Example

Break the problem into smaller parts

Divide & conquer Merge Sort, Quick Sort
and solve recursively.
Make the best choice at each step
Greedy Kruskal’s, Prim’s, Dijkstra
hoping for a global optimum.
Dynamic Break problem into overlapping
0/1 Knapsack, LCS
Programming subproblems and store results.
Try all possible options and backtrack
Backtracking N-Queens, Sudoku
if a solution fails.

Brute Force Try all possibilities blindly. Linear Search

1.2 What is Analysis (in Algorithms)?

Analysis is the process of evaluating how efficient the algorithm is in terms of:
 Time Complexity (how fast it runs)
 Space Complexity (how much memory it uses)
Design vs Analysis :
Design Analysis
Helps you build an algorithm. Helps you evaluate its efficiency.
Focuses on performance and
Focuses on logic and structure.
optimization.
Example: Choose Dynamic Programming to
Analyze it takes O(n2) time and O(n2) space.
solve a complex problem.

Summary:
 Design is about how to solve a problem.
 Analysis is about how good the solution is.

Prepared by : Kapil Dev Raghuwanshi

1
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

1.3 What is an Algorithm?

 An algorithm is a finite sequence of well-defined instructions that solves a computational
problem.
 It takes an input, processes it through a defined set of steps, and produces an output.

Formal Definition:
An algorithm is a step-by-step procedure to solve a problem in a finite number of steps.

An algorithm is a type of effective method in which a definite list of well-defined instructions for
completing a task; that given an initial state, will proceed through a well-defined series of
successive states, eventually terminating in an end-state. The concept of an algorithm originated
as a means of recording procedures for solving mathematical problems such as finding the
common divisor of two numbers or multiplying two numbers.
Algorithms are named for the 9th century Persian mathematician Al-Khowarizmi. He wrote a
treatise in Arabic in 825 AD, On Calculation with Hindu Numerals. It was translated into Latin
in the 12th century as Algoritmi de numero Indorum, which title was likely intended to mean
"[Book by] Algoritmus on the numbers of the Indians", where "Algoritmi" was the translator's
rendition of the author's name in the genitive case; but people misunderstanding the title treated
Algoritmi as a Latin plural and this led to the word "algorithm" (Latin algorismus) coming to
mean "calculation method".
Example:
Finding the maximum number in an array of size n.
Algorithm FindMax(A[1…n]):
1. max ← A[1] // assume first element is maximum
2. for i ← 2 to n do
3. if A[i] > max then
4. max ← A[i]
5. return max

Prepared by : Kapil Dev Raghuwanshi

2
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

1.3.1 Characteristics of an Algorithm

An algorithm must satisfy the following properties to be considered valid:
Input :
 An algorithm may have zero or more inputs.
 These are the values provided externally to solve the problem.
 Example: In Binary Search, input is the array + key element.
Output :
 An algorithm must produce at least one or more outputs.
 Output is the expected result after executing the steps.
 Example: In Binary Search, output is the index of the key or “not found.”
Definiteness :
 Each step of the algorithm must be precise, clear, and unambiguous.
 No vague instructions are allowed.
 Example: “Add 2 to x” is clear, but “do something with x” is not.
Finiteness :
 An algorithm must terminate after a finite number of steps.
 It should not go into an infinite loop.
 Example: A loop with proper termination condition.
Effectiveness (Feasibility)
 Every instruction must be very basic so that it can be carried out, in principle, by a person
using only pencil and paper.
 Each step must be basic and simple enough to be carried out by a computer (or a person,
theoretically).
 No complex or undefined operations should exist.
 Example: Multiplication of two numbers is effective; “multiply until you get infinity” is
not.
1.3.2 Advantages of Algorithms:
 It is easy to understand.
 An algorithm is a step-wise representation of a solution to a given problem.
 In an Algorithm the problem is broken down into smaller pieces or steps hence, it is easier
for the programmer to convert it into an actual program.

Prepared by : Kapil Dev Raghuwanshi

3
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

1.3.3 Disadvantages of Algorithms:

 Writing an algorithm takes a long time so it is time-consuming.

 Understanding complex logic through algorithms can be very difficult.
 Branching and Looping statements are difficult to show in Algorithms(imp).

1.3.4 Algorithm Specification

Algorithm can be described (Represent) in three ways
1. Natural language like English:
When this way is chooses, care should be taken, we should ensure that each & every
statement is is definite. (no ambiguity)
2. Graphic representation called flowchart:
This method will work well when the algorithm is small& simple.

3. Pseudo-code Method:

In this method, we should typically describe algorithms as program, which resembles language
like Pascal & Algol (Algorithmic Language).

Pseudo-Code Conventions:

1. Comments begin with // and continue until the end of line.

2. Blocks are indicated with matching braces { and }.
3. An identifier begins with a letter. The data types of variables are not explicitly
4. Compound data types can be formed with records.
Here is an example, data type – n data – n; node* link;
Node. Record {
data type – 1 data-1;
.
.
.
data type – n data – n;
node * link;
}

Here link is a pointer to the record type node. Individual data items of a record can be accessed
with → and period.

Prepared by : Kapil Dev Raghuwanshi

4
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

5. Assignment of values to variables is done using the assignment statement.

<Variable>:= <expression>;
6. There are two Boolean values TRUE and FALSE.
Logical Operators AND, OR, NOT
Relational Operators
<, <=,>,>=, =, !=
7. The following looping statements are employed. For, while and repeat-until
While Loop:
While < condition > do
{
<statement-1>
..
..
<statement-n>
}
For Loop:
For variable: = value-1 to value-2 step step do
{
<statement-1>
.
.
.
<statement-n>
}
repeat-until:
repeat
<statement-1>
.
.
.
<statement-n>

until<condition>
Prepared by : Kapil Dev Raghuwanshi
5
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

8. A conditional statement has the following forms.

 if <condition> then <statement>
 if <condition> then <statement-1>
 else <statement-1>

Case statement:
Case
{
: <condition-1> : <statement-1>
.
.
.
: <condition-n> : <statement-n>
: else : <statement-n+1>
}
10. Input and output are done using the instructions read & write. No format is used to specify
the size of input or output quantities
11. There is only one type of procedure: Algorithm, the heading takes the form,
Algorithm Name (Parameter lists)
consider an example, the following algorithm fields & returns the maximum of n given numbers:

1. algorithm Max(A,n)
2. // A is an array of size n
3. {
4. Result := A[1];
5. for i:= 2 to n do
6. if A[i] > Result then
7. Result :=A[i];
8. return Result;
9. }

Prepared by : Kapil Dev Raghuwanshi

6
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

1.4 The Role of Algorithms in Computing

In computing, an algorithm is a precise, step-by-step set of instructions designed to solve a
particular problem. Algorithms form the core of computer programs, guiding how data is
processed and tasks are executed. They ensure that problems are solved efficiently, correctly,
and consistently, regardless of the programming language or hardware used.
Algorithms play a critical role in:
 Problem solving – providing a systematic approach to reach a solution.
 Optimization – improving speed and reducing resource usage.
 Reusability – algorithms can be applied across multiple applications.
 Abstraction – focusing on logic rather than hardware detail
Algorithms are widely used in various industrial areas to improve efficiency, accuracy, and
decision-making. Some of the key applications include:
[Link]: Algorithms are used to optimize production processes and supply chain
management, reducing waste and increasing efficiency.
[Link]: Algorithms are used to analyze financial data and make predictions, enabling traders
and investors to make informed decisions.
[Link]: Algorithms are used to process and analyze medical images, assist in diagnosing
diseases, and optimize treatment plans.
4. Retail: Algorithms are used for customer relationship management, personalized product
recommendations, and pricing optimization.
[Link]: Algorithms are used to optimize routes for delivery and transportation,
reducing fuel consumption and increasing delivery speed.
[Link]: Algorithms are used to optimize energy generation, distribution, and consumption,
reducing waste and increasing efficiency.
[Link]: Algorithms are used to detect and prevent security threats, such as hacking, fraud,
and cyber-attacks
1.5 Model of Computation
A Model of Computation is an abstract framework used to design, describe, and analyze
algorithms. It specifies:
 What operations are allowed ((like arithmetic operations, comparisons, memory access,
etc.).
 How computation is carried out
 What is counted as a basic operation (step)

Prepared by : Kapil Dev Raghuwanshi

7
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

This helps in evaluating algorithm performance in a machine-independent way.

It serves as a reference to perform algorithm analysis and predict the complexity of an
algorithm.
Why is a Model of Computation Important?
 To analyse time and space complexity in a standardized way.
 To compare algorithms fairly across different systems.
 To ensure algorithms are platform-independent.
Common Models of Computation:
a) RAM Model (Random Access Machine)
This is the most widely used model in algorithm analysis.
 Assumes that:
1. Each basic operation (addition, subtraction, comparison, assignment) takes constant time.
2. Memory can be accessed in constant time (random access).
3. Instructions are executed sequentially.
 Widely used for analyzing algorithms like sorting, searching, and dynamic programming.
b) Turing Machine
 A theoretical model of computation introduced by Alan Turing.
 Consists of:
o An infinite tape for input and memory.
o A head that reads and writes symbols on the tape.
o A finite set of states to control the computation.
 Used to define computability and algorithm complexity in theory (e.g., P vs NP problems).
1.6 Analysis of algorithms : The analysis of algorithms is the process of evaluating and
understanding the efficiency and performance of an algorithm. It helps determine how
well an algorithm performs in terms of time and space requirements and how it scales with
different input sizes. Essentially, it answers questions like: “How fast is this algorithm?” and
“How much memory does it consume?”

Purpose of Algorithm Analysis

 To predict performance without implementing the algorithm.
 To compare different algorithms solving the same problem.
 To optimize algorithms for speed, memory usage, or other resources.
 To understand scalability as input size grows.

Prepared by : Kapil Dev Raghuwanshi

8
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

1.7 Complexity
Complexity measures the resources consumed by an algorithm when solving a problem.
In the other words complexity usually refers to the resource usage of an algorithm as a function of
the input size. Analysing complexity helps us compare algorithms and choose the most efficient
one. There are two main types: time complexity and space complexity
Time Complexity – How long an algorithm takes to run.
Space Complexity – How much memory an algorithm uses.

The main resources are:

1.7.1 Time Complexity – Number of basic operations executed.

Time Complexity is the amount of time taken by an algorithm to execute, depending on the size
of the input.
 Measures the amount of time an algorithm takes to complete as a function of input size
n.
 Focuses on how the number of operations grows with input
Factors affecting time complexity:
 Number of elementary operations (comparisons, assignments, arithmetic operations)
 Loops and nested loops
 Recursive calls

Common terms :
 Best Case: Minimum time (most favourable input).
 Worst Case: Maximum time (least favourable input).
 Average Case: Expected time over all possible inputs.
1. Best Case
Definition:
The best case is the scenario where the algorithm performs the minimum number of steps possible.
This happens when the input is most favourable.
 The minimum time an algorithm takes to complete.
 Occurs when the input is in the most favorable configuration.
 In the best-case analysis, we calculate the lower bound on the running time of an algorithm.
 We must know the case that causes a minimum number of operations to be executed.
 Time Complexity: Minimum time the algorithm will take.
Example:
Consider linear search in an array:
Array: [5, 3, 2, 7, 1]

Prepared by : Kapil Dev Raghuwanshi

9
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Search for: 5
 Here, the element we search for is at the first position.
 Algorithm finds it in 1 comparison → this is the best case.
 Complexity: O(1)

2. Worst Case
Definition:
 The worst case is the scenario where the algorithm performs the maximum number of steps. This
occurs for the least favourable input.
 In the worst-case analysis, we calculate the upper bound on the running time of an algorithm. We
must know the case that causes a maximum number of operations to be executed.
 Time Complexity: Maximum time the algorithm will take.
Example:
Using the same linear search:
Array: [5, 3, 2, 7, 1]
Search for: 1
 Here, the element is at the last position.
 Algorithm checks all n elements → this is the worst case.
 Complexity: O(n)

3. Average Case :
 The average case represents the expected number of steps over all possible inputs. It assumes
all inputs are equally likely.
 Time Complexity: Expected time to process a random input.
 In average case analysis, we take all possible inputs and calculate the computing time for all
of the inputs. Sum all the calculated values and divide the sum by the total number of inputs.
Example with Linear Search:
 Suppose we have n elements and each element is equally likely to be searched.
Assumptions
 n = total number of elements in the list
 P = probability of a successful search (element is present)
 Probability of unsuccessful search = (1−P)

Prepared by : Kapil Dev Raghuwanshi

10
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Step 1: Successful Search

If the element is found at the ith location, then:
Probability of this happening = P/n
 Time taken = I comparisons.
 Therefore, total cost for successful search =

Step 2: Unsuccessful Search

 If the element is not present, then we need to check all n elements.
 Time taken = n comparisons.
 Probability of this = (1−P)
 Contribution = n(1−P)
Step 3: Combine Both

Prepared by : Kapil Dev Raghuwanshi

11
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Interpretation
 When P=1 it means the search is always successful (the element is guaranteed to be in the list).
 On average, the element will be found in the middle position of the list.
 Hence, the average number of comparisons is:

Time complexity of an algorithm can be calculated by using two methods:

1. Posteriori Analysis
2. Priori Analysis

A Posteriori analysis A priori analysis

Posteriori analysis is a relative analysis. Priori analysis is an absolute analysis.

It is dependent on language of compiler and type of It is independent of language of compiler and types
hardware. of hardware.
It will give exact answer. It will give approximate answer.
It uses the asymptotic notations to represent how
It doesn't use asymptotic notations to represent the
much time the algorithm will take in order to
time complexity of an algorithm.
complete its execution.
The time complexity of an algorithm using a The time complexity of an algorithm using a priori
posteriori analysis differ from system to system. analysis is same for every system.
If the time taken by the program is less, then the credit If the algorithm running faster, credit goes to the
will go to compiler and hardware. programmer.
It is done after execution of an algorithm. It is done before execution of an algorithm.
It is costlier than priori analysis because of
It is cheaper than Posteriori Analysis.
requirement of software and hardware for execution.
Maintenance Phase is not required to tune the
Maintenance Phase is required to tune the algorithm.
algorithm.

Prepared by : Kapil Dev Raghuwanshi

12
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

1 .7.2 Space Complexity – Amount of memory used.

Space Complexity of an algorithm is the total amount of memory space required by the algorithm
to execute completely, as a function of the input size. It includes the memory needed for:

Space complexity S(p) == Auxiliary space + Memory used by input variables

Input variables – The memory used to store the input data.

Auxiliary space – Temporary memory used during computation, such as variables, arrays,
recursion stack, or other temporary structures.
Components of Space Complexity
The space required by an algorithm is the sum of the following components:

1. Fixed Part:
o Memory that is independent of input and output.
o Includes memory for:
 Program code
 Constants
 Simple variables
2. Variable Part:
o Memory that depends on input, output, and recursion stack.
o These parameters are called instance characteristics.
Space Requirement Formula
S(P)=c+Sp
Where:
 S(P)= Space required by algorithm P
 c = Constant memory for the fixed part
 Sp = Memory required for instance characteristics (input, output, recursion stack, temporary
storage)

Prepared by : Kapil Dev Raghuwanshi

13
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

1.8 Concept of Frequency Count

The time complexity of an algorithm can be computed using the frequency count.
Definition : The frequency count is a count that denotes how many times a particular statement
is executed.
In other words, instead of just looking at the code structure, we count how many times each line
(or block) runs, which helps us determine the algorithm’s time complexity.
Step count:
 For algorithm heading → 0

 For braces { } → 0

 For expressions → 1

 For any looping statements → Number of times the loop is repeating

Example : comments = 0 step

 Assignment statement= 1 step

 condition statement= 1 step

 loop condition for n times = n+1 steps

 body of the loop = n steps

Consider the following code for counting the frequency count
void fun()
{
int a;
a = 10;
printf("%d", a);
}
Solution :
void fun()
{
int a;
a = 10; …………………………………… Executes once
printf("%d", a); …………………………………… Executes once
}
The frequency count of above program is 2.

Prepared by : Kapil Dev Raghuwanshi

14
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Example 1.8.1
Obtain the frequency count for the following code.
void fun()
{
int a;
a = 0;

for(i = 0; i < n; i++)

{
a = a + i;
}
printf("%d", a);
}
Solution :
void fun()
{
int a;
a = 0; ………………………………………… 1
for(i = 0; i < n; i++) ………………………………………… n + 1
{
a = a + i; ………………………………………… n
}
printf("%d", a); ………………………………………… 1
}
The frequency count of the above code is 2n + 3.

Example 1.8.2 Obtain the frequency count for the following code.
OR
Using Step count method analyze the time complexity when two men matrices are added.
void fun(int a[][],int b[][])
{
int c[3][3];
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
c[i][j]=a[i][j]+b[i][j];
}}

Prepared by : Kapil Dev Raghuwanshi

15
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Solution :
void fun(int a[][],int b[][])
{
int c[3][3];
for(i=0;i<m;i++) ……………………….. (m+1)
{
for(j=0;j<n;j++) ………………………….m.(n+1)
{
c[i][j]=a[i][j]+b[i][j]; …………………. m.n
}}
The frequency count = (m + 1) + m(n+1)+mn = 2m + 2mn + 1 = 2m(1 + n) + 1
Example 1.8.3 Obtain the frequency count for the following code.
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
c[i][j]=0;
for(k=1;k<=n;k++)
c [i][j]= c[i][j] +a[i][k] * b[k]lj];
}
}
}
Solution :
for(i=1;i<=n;i++)………………………………….n+1
{
for(j=1;j<=n;j++)…………………………………n(n+1)
{
c[i][j]=0;………………………………………… n.n

Prepared by : Kapil Dev Raghuwanshi

16
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

for(k=1;k<=n;k++)………………………………….. n.n(n+1)
c [i][j]= c[i][j] +a[i][k] * b[k]lj];…………………. n.n.n
}
}
}

The frequency count = 2n3 + 3n2+2n+1

Example 1.8.4 Obtain the frequency count for the following code.
int sum(int A[],int n)
{
int sum=0,i;
for (i=0;i<n;i++)
sum=sum+A[i];
return sum;
}
Solution :
int sum(int A[],int n)
{
int sum=0,i;……………………………….1
for (i=0;i<n;i++)…………………..n+1
sum=sum+A[i];………………….. n
return sum;…………………….1
}
2n+3
The frequency count = 2n+3

Prepared by : Kapil Dev Raghuwanshi

17
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

1.9 Growth of Function

In algorithm analysis, growth of function refers to how the running time or space requirements
of an algorithm increase with the size of the input. We analyse this growth using asymptotic
notations.
What is rate of growth :
The rate at which running time increases as a function of input is called Rate of Growth or
Order of Growth.
Rate of growth is defined as the rate at which the running time of the algorithm is increased when
the input size is increased.
Consider the example of buying elephants and goldfish:
Cost: cost_of_elephants + cost_of_goldfish
Cost ~ cost_of_elephants (approximation)
 The low order terms in a function are relatively insignificant for large n
n4 + 100n2 + 10n + 50 ~ n4
i.e., we say that n4 + 100n2 + 10n + 50 and n4 have the same rate of growth .
Commonly used Rate of Growths :
Below is the list of rate of growths which we will see further.

Time
Name Example
Complexity

Adding an element to the front of a linked

1 Constant
list

log n Logarithmic Finding an element in a sorted array

n Linear Finding an element in a unsorted array

nlog n Linear Logarithmic Sorting n items by ‘Divide and Conquer’

n2 Quadratic Shortest path between 2 nodes in a graph

n3 Cubic Matrix Multiplication

Prepared by : Kapil Dev Raghuwanshi

18
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

2n Exponential The Towers of Hanoi problem

Prepared by : Kapil Dev Raghuwanshi

19
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Table : Order of Growth

1.9 Asymptotic notation :

Asymptotic notations are mathematical tools used in computer science to describe the
performance or complexity of algorithms, particularly how their running time or space
requirements grow as the input size increases. These notations focus on the "asymptotic
behavior" of functions, meaning their behavior for very large input sizes, ignoring constant
factors and lower-order terms.
Asymptotic notations are used to write fastest and slowest possible running time for an
algorithm. These are also referred to as 'best case' and 'worst case' scenarios respectively.
"In asymptotic notations, we derive the complexity concerning the size of the input. (Example in
terms of n)"
"These notations are important because without expanding the cost of running the algorithm, we
can estimate the complexity of the algorithms."

Prepared by : Kapil Dev Raghuwanshi

20
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

In the analysis of algorithms, asymptotic notation provides a framework to describe the growth
rate of an algorithm’s running time or space requirement as the input size 𝑛
becomes large. It ignores machine-dependent constants and focuses on the mathematical
behaviour of functions.
Why is Asymptotic Notation Important?
1. They give simple characteristics of an algorithm's efficiency.
2. They allow the comparisons of the performances of various algorithms.
Types of Asymptotic Notations :
[Link] oh (O)notation
[Link] omega (Ω) notation
[Link](Θ) notation
[Link] oh notation
[Link] omega(Ω) notation
They are 3 asymptotic notations are mostly used to represent time complexity of algorithm.
Big oh (O) Notation :
Definition :
A function f(n)is said to be Big-O of g(n), written as
f(n)=O(g(n)) (read as f of n is big O of g of n)
if and only if (iff) there exist positive constants c>0and n0≥0 such that:
f(n) ≤ c*g(n) for all n ≥ n0.

 Big-O notation represents the upper bound of the running time of an algorithm.
Prepared by : Kapil Dev Raghuwanshi
21
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

 Therefore, it gives the worst-case complexity of an algorithm.

 It is the most widely used notation for Asymptotic analysis.
 It returns the highest possible output value(big-O) for a given input.
 Big-O(Worst Case) It is defined as the condition that allows an algorithm to complete
statement execution in the longest amount of time possible.
Example 1 :
Let f(n)=3n+2
Choose g(n)=n

For n≥1
3n+2≤5n (take c=5, n0=1).
So, 3n+2=O(n).

Big omega (Ω) notation :

Definition: Big-Omega (Ω) Notation

 Big-Omega gives a lower bound on the growth of a function.

 The notation Ω(n) is the formal way to express the lower bound of an algorithm's
running time.
 It measures the best-case time complexity or the best amount of time an algorithm can
possibly take to complete.

Prepared by : Kapil Dev Raghuwanshi

22
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Prepared by : Kapil Dev Raghuwanshi

23
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Theta (Θ) Notation :

Definition: Big-Theta (Θ) Notation :

 Big-Theta gives a tight bound on the growth of a function.

 It means f(n) grows at the same rate as g(n), up to constant factors.

 In other words, g(n) is both an upper bound and a lower bound for f(n).

 The notation (n) is the formal way to express both the lower bound and the upper bound of an
algorithm's running time.
 Some may confuse the theta notation as the average case time complexity; while big theta
notation could be almost accurately used to describe the average case, other notations could be
used as well.

Prepared by : Kapil Dev Raghuwanshi

24
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Little-o Notation ( o ) :

 Little-oh is a strict upper bound.

 It means f(n) grows strictly slower than g(n).
 Unlike Big-O, equality at the same order of growth is not allowed.

Prepared by : Kapil Dev Raghuwanshi

25
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Little-Omega (ω) Notation :

Definition: Little-Omega (ω) Notation :

 Little-omega gives a strict lower bound.

 It means f(n)f(n)f(n) grows strictly faster than g(n)g(n)g(n).
 Unlike Big-Ω, equality in growth is not enough here.

Prepared by : Kapil Dev Raghuwanshi

26
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Mathematical Condition :

Prepared by : Kapil Dev Raghuwanshi

27
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Comparison of Asymptotic Notations:

Graphical Intuition
 Big-O (O) → f(n) curve stays below or equal to some multiple of g(n).

 Big-Ω (Ω) → f(n) curve stays above or equal to some multiple of g(n).

 Big-Θ (Θ) → f(n) curve is sandwiched between two multiples of g(n).

 Little-o (o) → f(n) grows strictly slower, never catching up with g(n).

 Little-ω (ω) → f(n) grows strictly faster, eventually leaving g(n) behind.

Common orders of magnitude

Prepared by : Kapil Dev Raghuwanshi

28
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Prepared by : Kapil Dev Raghuwanshi

29
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Prepared by : Kapil Dev Raghuwanshi

30