UNIT 1
Introduction to Algorithm
Analysis
[~6 Marks]
Prepared by: Er. Sumit Sharma
Introduction to Algorithm Analysis
• 1.1 Algorithm and its properties, RAM model, time and space complexity,
detailed analysis of algorithms, Concept of Aggregate Analysis
• 1.2 Asymptotic notations (Big-O, Big-Ω and Big-Ө), their geometrical
interpretations and examples
• 1.3 Concept of best case, average case and worst-case performance of an
algorithm
• 1.4 Modeling algorithms by recurrence relation
• 1.5 Solving recurrence relation for evaluating computational complexity
• 1.5.1 Recursion tree method
• 1.5.2 Substitution method
• 1.5.3 Using masters theorem
1.1
• Algorithm and its properties
• RAM model
• Time and Space complexity
• Detailed analysis of algorithms
• Concept of Aggregate Analysis
Algorithm and its properties
What is an Algorithm?
A finite set of instructions where each instruction can be executed in finite time
to perform computation taking some value(s) as input and producing value(s)
as output.
Properties / Characteristics of an Algorithm
• Input / Output: Must accept input value(s) and produce output value(s)
• Correctness: Must produce output according to the requirement of the
algorithm
• Finiteness: Must complete after a finite number of instructions have
been executed
• Feasibility: Every instruction must be feasible to execute
• Flexibility: Changes should be possible without much effort
• Efficiency: Should use lesser running time and memory space as much as
possible
RAM Model (Random Access Machine)
A model for counting the steps in an algorithm in order to analyze its
complexity.
• Basic operations (+, −, ×, ÷) each count as 1 step
• Memory reference (read & write) counts as 1 step
• Loops and function calls are NOT basic operations: not counted individually
• NOTE:
• The loop itself is not counted as 1 step. Instead, we count the operations
performed during all its iterations.
• Example: Factorial algorithm step count = 7n + 3
Time & Space Complexity
• Measuring algorithmic performance
Time Complexity Space Complexity
• Total time an algorithm takes to solve a problem • Total memory space required by an algorithm to solve a
• Measured in terms of number of computational steps problem
• Best Case: lower bound on running time (Ω) • Measured in terms of number of data variables used
during computation
• Worst Case: upper bound on running time (O)
• Constant variables → O(1)
• Average Case: average steps for any instance of input
• Array of n elements → O(n)
Detailed Time Complexity Analysis
• Simple operations (assignment, addition, printf, scanf, return)
• take constant time → negligible
• We analyze loops: for, while, etc.
• Simple loop
• for(i=0; i<n; i++) → O(n)
• Nested loops
• (two O(n) loops) → O(n) × O(n) = O(n²)
Time
• for(i=0; i<n; i++) {
for(j=0; j<n; j++) Complexity
}
• Loop incrementing by multiplication
• for(i=0; i<=n; i*5) → O(log₅n)
• O(logconstant multipliern)
Detailed Space Complexity Analysis
• Space complexity = total memory references used by the algorithm
• Constant number of variables
• (e.g., 1, 2, 3, 4, 5 …) → O(1)
• Array taking n memory references → O(n)
• Example:
• Factorial algorithm:
• uses variables i, n, fact → 3 references → O(1)
Space
Complexity
Asymptotic Notations
Asymptotic Notations are mathematical tools used to analyze the performance of algorithms by understanding
how their efficiency changes as the input size grows.
• By using asymptotic notations, such as Big O, Big Omega, and Big Theta, we can categorize algorithms based
on their worst-case, best-case, or average-case time or space complexities, providing valuable insights into
their efficiency.
There are mainly three asymptotic notations:
[Link]-O Notation (O-notation)
[Link] Notation (Ω-notation)
[Link] Notation (Θ-notation)
Big-O Notation (Upper Bound)
Mathematical Representation of Big-O notation :
O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }
• Big-O notation represents the upper bound of the running time of an
algorithm. Therefore, it gives the worst-case complexity of an
algorithm.
• 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.
• Examples:
• { 100 , log (2000) , 10^4 } belongs to O(1)
{ (n/4) , (2n+3) , (n/100 + log(n)) } belongs to O(n)
{ (n^2+n) , (2n^2) , (n^2+log(n))} belongs to O( n^2)
• F(n) = 2n2+n, thus F(n) = O(n2)
Big- Ω Notation (lower Bound)
Mathematical Representation of Omega notation :
Ω(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0 }
• Omega notation represents the lower bound of the running time
of an algorithm. Thus, it provides the best-case complexity of an
algorithm.
• It is defined as the condition that allows an algorithm to
complete statement execution in the shortest amount of time.
• Example:
• { (n^2+n) , (2n^2) , (n^2+log(n))} belongs to Ω( n^2)
{ (n/4) , (2n+3) , (n/100 + log(n)) } belongs to Ω(n)
{ 100 , log (2000) , 10^4 } belongs to Ω(1)
Big- Θ Notation (Both upper and lower bound)
• Θ (g(n)) = {f(n): there exist positive constants c1, c2 and n0
• such that 0 ≤ c1 * g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n0}
• Note: Θ(g) is a set
• Theta notation encloses the function from above and below.
Since it represents the upper and the lower bound of the
running time of an algorithm
• It is used for analyzing the average-case complexity of an
algorithm.
• { 100 , log (2000) , 10^4 } belongs to Θ(1)
{ (n/4) , (2n+3) , (n/100 + log(n)) } belongs to Θ(n)
{ (n^2+n) , (2n^2) , (n^2+log(n))} belongs to Θ( n2)
Examples
Growth Type Example Function f(n) Big-O (Upper Bound) Ω (Lower Bound) Θ (Tight Bound)
1 (Constant) ( f(n)=5 ) O(1) Ω(1) Θ(1)
log n ( f(n)=\log n + 3 ) O(log n) Ω(log n) Θ(log n)
n (Linear) ( f(n)=3n+10 ) O(n) Ω(n) Θ(n)
n log n ( f(n)=n\log n + n ) O(n log n) Ω(n log n) Θ(n log n)
n² (Quadratic) ( f(n)=n^2 + 5n ) O(n²) Ω(n²) Θ(n²)
n³ (Cubic) ( f(n)=2n^3 + n ) O(n³) Ω(n³) Θ(n³)
n⁴ ( f(n)=n^4 + n^2 ) O(n⁴) Ω(n⁴) Θ(n⁴)
2ⁿ (Exponential) ( f(n)=2^n + n^2 ) O(2ⁿ) Ω(2ⁿ) Θ(2ⁿ)
n! (Factorial) ( f(n)=n! + 2^n ) O(n!) Ω(n!) Θ(n!)
1 < logn < n < nlogn < n2 < n3 < n4 < 2n < n!
Aggregate Analysis
Determines the upper bound T(n) on total cost of n operations, then calculates average cost = T(n)/n. Each
operation gets the same average cost.
• Step 1: Show that a sequence of n operations takes T(n) time in worst case
• Step 2: Show each operation takes T(n)/n time on average
• Example:
• Stack with Push & Pop operations (both O(1) each):
• n total operations → T(n) = O(n)
• Average cost = O(n)/n = O(1) per operation
• Need of Aggregate Analysis
Some algorithms have:
• Most operations = cheap
• Few operations = very expensive
• Though overall performance is still good.
Recursive Algorithms &
Recurrences
Solving recurrences with 4 methods
Recursive Algorithms
• Recursion is the process of defining a problem in terms of itself
• A function that calls itself directly or indirectly.
• Complex problems are divided into smaller sub-problems.
• Classic examples: Towers of Hanoi, Tree Traversals, DFS of a Graph
• Every recursive algorithm needs a base case to terminate
• Factorial (recursive): if (n<=1) return 1; else return n * fact(n-1)
• Recurrence for factorial: T(n)=1 when n=1 ; T(n)=T(n-1)+O(1) when n>1
Methods for Solving Recurrences
• Iteration Method:
• Expand the relation until boundary is met; sum the series
• Recursion Tree Method:
• Pictorial tree representation of iteration; sum costs at each level
• Substitution Method:
• Guess a solution form, then prove by mathematical induction
• Master Method:
• Direct formula for T(n) = aT(n/b) + f(n) where a≥1, b>1
To be Continued…