DAA 22CSE52

MODULE 1

Exploring Algorithms and Analyzing Function Growth

SYLLABUS: Algorithm introduction, Fundamentals of Algorithmic problem solving,

Asymptotic notations, Standard notations and common functions, Important problem
types, string processing, graph problems, combinatorial problems, Recurrence-
Substitution method, Recursive tree, Mathematical Analysis of Recursive and Non-
Recursive Algorithms.

1.1 Algorithm Introduction

Definition

An algorithm is a step-by-step procedure or set of instructions designed to perform a

specific task or solve a particular problem.

It takes input(s), processes them through a sequence of defined steps, and produces the
desired output.

Characteristics of a Good Algorithm

1. Input – It should accept zero or more inputs.

2. Output – It should produce at least one output.
3. Finiteness – It should terminate after a finite number of steps.
4. Definiteness – Every step should be clear, unambiguous, and precisely defined.
5. Effectiveness – Each step should be basic enough to be performed in a reasonable
amount of time.
6. Generality – It should solve all instances of the problem, not just a specific case.

Page 1 of 48
DAA 22CSE52

Importance of Algorithms

✔ Provides a structured approach to problem-solving.

✔ Improves code efficiency in terms of time and space.

✔ Enhances readability and maintainability of programs.

✔ Helps in debugging and testing.

✔ Forms the foundation of programming and computer science.

✅ Applications of Algorithms

• Searching and sorting data

• Routing and navigation systems
• Text processing
• Data compression
• Artificial Intelligence and Machine Learning
• Network protocols
• Games and simulations

Page 2 of 48
DAA 22CSE52

GCD of Two Numbers

The Greatest Common Divisor (GCD) of two numbers is the largest number that divides
both without leaving a remainder.

Example:
GCD(12, 18) = 6

1. Euclid’s Algorithm

➤ Principle

The GCD of two numbers A and B is the same as the GCD of B and A mod B.

Mathematically:
GCD(A, B) = GCD(B, A mod B)

This process is repeated until the remainder becomes 0.

➤ Steps

1. Read A and B.
2. While B ≠ 0:
o Find remainder r = A mod B.
o Replace A with B and B with r.
3. When B = 0 → GCD = A.

Page 3 of 48
DAA 22CSE52

➤ Pseudocode

Input: A, B
while B ≠ 0
r=A%B
A=B
B=r
print A

➤ Example

A = 48, B = 18

• Step 1 → r = 48 % 18 = 12 → A = 18, B = 12
• Step 2 → r = 18 % 12 = 6 → A = 12, B = 6
• Step 3 → r = 12 % 6 = 0 → A = 6, B = 0

GCD = 6

➤ Time Complexity

• Worst case → O(log min(A, B))

• Fast and efficient for large numbers.

Page 4 of 48
DAA 22CSE52

2. Consecutive Integer Checking Method

➤ Principle

Start checking from the smaller of A and B downwards and find the largest integer that
divides both.

➤ Steps

1. Read A and B.
2. Find the smaller of A and B → min.
3. Check from min down to 1:
o If both A and B are divisible by i → GCD = i.

➤ Pseudocode

Input: A, B
min = smaller of A and B
for i = min down to 1
if A % i == 0 and B % i == 0
print i
break

➤ Example

A = 48, B = 18

• min = 18
• Check: 18 → no, 17 → no, 16 → no, ..., 6 → yes
GCD = 6

Page 5 of 48
DAA 22CSE52

➤ Time Complexity

• Worst case → O(min(A, B))

• Simple but inefficient for large numbers.

3. Middle School Procedure

➤ Principle

This method uses prime factorization of both numbers and multiplies the common prime
factors.

➤ Steps

1. Find prime factors of A.

2. Find prime factors of B.
3. Identify common factors.
4. Multiply the common factors → GCD.

➤ Example

A = 48 → prime factors = 2 × 2 × 2 × 2 × 3
B = 18 → prime factors = 2 × 3 × 3

Common factors → 2 × 3 = 6
GCD = 6

➤ Pseudocode

Input: A, B
Find prime factors of A → listA

Page 6 of 48
DAA 22CSE52

Find prime factors of B → listB

common = product of common factors in listA and listB
print common

➤ Time Complexity

• Depends on how factorization is implemented.

• Not efficient for large numbers.
• Good for small numbers and educational purposes.

Comparison of 3 Methods

Algorithm Principle Efficiency Suitable for

Division &
Euclid’s Algorithm O(log n) Large numbers
remainder

Consecutive Integer
Check from min to 1 O(n) Small inputs
Check

Middle School Depends on Educational

Prime factorization
Procedure factorization problems

Page 7 of 48
DAA 22CSE52

Prime Numbers – Sieve of Eratosthenes

Definition:
A prime number is a natural number greater than 1 that has no positive divisors other
than 1 and itself.

Examples:

2, 3, 5, 7, 11, 13, 17, 19, 23...

✅ What is the Sieve of Eratosthenes?

It is an efficient algorithm to find all prime numbers up to a given limit n.

It works by repeatedly marking the multiples of each prime number starting from 2.

✅ Principle

1. Start with all numbers from 2 to n.

2. Pick the first unmarked number (starting from 2), mark it as prime.
3. Mark all multiples of this prime as non-prime.
4. Move to the next unmarked number and repeat steps 2 and 3.
5. Continue until you process all numbers up to √n.

✅ Steps of the Algorithm

1. Create a list of integers from 2 to n.

2. Initially, mark all numbers as prime.
3. Start with p = 2 (the first prime number).
4. Mark all multiples of p greater than or equal to p² as non-prime.
5. Find the next unmarked number and set p to that number.
6. Repeat until p² > n.
Page 8 of 48
DAA 22CSE52

7. The unmarked numbers in the list are the prime numbers.

Pseudocode

Input: n
Create a list isPrime[2...n], initialized to True
for p = 2 to sqrt(n)
if isPrime[p] == True
for i = p*p to n step p
isPrime[i] = False
for p = 2 to n
if isPrime[p] == True
print p

✅ Example – Find all primes up to 30

Step 1 → Initialize:
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
30

Step 2 → Start with p = 2, mark multiples of 2 → 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28,
30.

Step 3 → Next p = 3, mark multiples → 9, 12, 15, 18, 21, 24, 27, 30.

Step 4 → Next p = 5, mark multiples → 25, 30.

Stop when p² > n → √30 ≈ 5.47 → stop at p = 5.

Unmarked numbers →2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Time Complexity

Page 9 of 48
DAA 22CSE52

• Worst case → O(n log log n)

• Much faster than checking each number individually.

✅ Space Complexity

• O(n), as it stores information for each number from 2 to n.

✅ Applications

✔ Finding prime numbers up to a large limit

✔ Cryptography algorithms like RSA

✔ Factoring problems
✔ Mathematical computations requiring primes

Advantages

✔ Efficient for large n

✔ Easy to implement

✔ Can be extended to segmented sieves or optimized further

Disadvantages

✘ Requires memory proportional to n

✘ Not suitable for finding primes in a very large range without optimizations

Page 10 of 48
DAA 22CSE52

Analysis of Algorithms – Space and Time Efficiency

1. Introduction

Algorithm analysis helps us understand how efficiently an algorithm performs when the
input size increases. The two important aspects are:

1. Time Efficiency – How fast the algorithm executes.

2. Space Efficiency – How much m
3. emory the algorithm consumes.

2. Space Efficiency

➤ Definition

Space efficiency measures the amount of memory required by an algorithm to solve a

problem based on the size of input.

It includes:

• Memory for input data.

• Memory for auxiliary or temporary variables.
• Memory for recursion or function calls.

➤ Space Complexity

• Expressed as a function of input size n.

• Helps to understand the maximum memory required during execution.

➤ Example

Problem: Find the sum of n elements in an array.

Page 11 of 48
DAA 22CSE52

Input: array of size n

Variables: sum, index
Output: sum of elements

Space used:

• Input array → O(n)

• Variables → O(1)
Total space complexity → O(n)

3. Time Efficiency

➤ Definition

Time efficiency measures the number of basic operations an algorithm performs with
respect to the size of the input.

It estimates how quickly the algorithm can provide the output.

➤ Time Complexity

• Expressed as a function of input size n.

• Helps compare algorithms based on execution time.
• 4. Basic Operation

➤ Definition

A basic operation is a single step in an algorithm that takes constant time to execute.
These are the most fundamental actions like:

• Arithmetic operations (+, −, *, /)

• Comparisons (<, >, ==)
• Assignments (=)
Page 12 of 48
DAA 22CSE52

• Reading/writing a variable or input/output

➤ Example

Problem: Find the maximum element in an array.

max = arr[0]
for i = 1 to n-1
if arr[i] > max
max = arr[i]

Basic operation → comparison arr[i] > max.

• Runs (n − 1) times.
• Time complexity → O(n).

5. Order of Growth

➤ Definition

Order of growth describes how the running time or space requirement grows with input
size.

It helps to classify algorithms based on their efficiency rather than exact execution time.

➤ Common Orders of Growth

Order Description Example

O(1) Constant time Accessing array element

O(log n) Logarithmic time Binary search

O(n) Linear time Traversing an array

O(n log n) Linearithmic time Merge sort

Page 13 of 48
DAA 22CSE52

Order Description Example

O(n²) Quadratic time Bubble sort

O(2ⁿ) Exponential time Recursive Fibonacci

➤ How to Find the Order of Growth

1. Identify loops and recursion.

2. Count how often the basic operation is executed.
3. Express the count as a function of input size n.
4. Drop constants and less significant terms.

➤ Example – Sum of First n Natural Numbers

sum = 0
for i = 1 to n
sum = sum + i

• Loop runs n times → basic operation executed n times.

• Time complexity → O(n).
• Space complexity → O(1) (only a few variables used).

6. Why Focus on Order of Growth?

✔ It helps compare algorithms independent of machine-specific factors like CPU speed.

✔ Shows scalability for larger datasets.

✔ Guides optimization efforts.

✔ Helps understand algorithm efficiency at a glance.

Page 14 of 48
DAA 22CSE52

7. Relationship Between Time and Space

• Some algorithms may use more memory to reduce time complexity (e.g., caching
intermediate results).
• Others may optimize space at the cost of time by recalculating values instead of
storing them.
• Analyzing both helps find a balanced solution based on problem requirements.

Important Problem Types

• Searching problems
• Sorting problems
• String matching problems
• Graph traversal problems
• Pathfinding problems
• Dynamic programming problems
• Combinatorial problems

String Processing

• Manipulation of text data.

• Operations:
o Pattern matching (e.g., KMP algorithm)
o Substring search
o Palindrome check
o Anagram detection
• Use cases:
o Text editors
o DNA sequence analysis
o Search engines

Page 15 of 48
DAA 22CSE52

Graph Problems

• Graph = Set of nodes (vertices) and edges.

• Types of graphs:
o Directed or undirected.
o Weighted or unweighted.
• Important problems:
o Depth-first search (DFS)
o Breadth-first search (BFS)
o Shortest path (Dijkstra’s algorithm)
o Minimum spanning tree (Kruskal’s, Prim’s algorithm)
• Applications:
o Social networks
o Routing and navigation
o Circuit design

Problems

• Involves counting or arrangement of objects.

• Problems:
o Permutations and combinations
o Subset generation
o Graph coloring
o Knapsack problem
• Approach:
o Recursion
o Backtracking
o Dynamic programming

Page 16 of 48
DAA 22CSE52

Recurrence – Substitution Method

• Solving recursive relations by guessing the form of the solution and proving by
substitution.
• Example:
• T(n) = 2T(n/2) + n
• Guess: T(n) = O(n log n)
• Substitute and prove.

10. Recursive Tree Method

• Visual representation of recursive calls.

• Helps to understand how the problem size reduces at each step.
• Example:
• T(n) = T(n/2) + 1
• Tree depth = log n
• Total work = log n

11. Mathematical Analysis of Recursive and Non-Recursive Algorithms

• Recursive analysis:
o Find recurrence relation.
o Solve it using substitution or tree method.
o Example: Merge sort → O(n log n)
• Non-recursive analysis:
o Count iterations in loops.
o Multiply the number of operations by input size.
o Example: Linear search → O(n)
• Comparisons:

Page 17 of 48
DAA 22CSE52

Algorithm Type Time Complexity Example

Recursive T(n) = 2T(n/2) + n → O(n log n)

Non-recursive Loop runs n times → O(n)

What is Mathematical Analysis of Recursive Algorithms?

Recursive algorithms solve problems by breaking them into smaller sub-problems and
calling themselves with reduced input size.

Mathematical analysis helps us:

✔ Understand how much time or space the recursive algorithm takes
✔ Write and solve recurrence relations to find the algorithm’s complexity

✔ Predict the performance for larger inputs

Steps in Mathematical Analysis of Recursive Algorithms

1. Identify the recurrence relation

→ Write how the algorithm calls itself and how much work it does at each step.
2. Find base cases
→ Where the recursion stops and returns a result without further calls.
3. Solve the recurrence
→ Using methods like substitution, recursion tree, or mathematical formulas.
4. Analyze the time and space complexity
→ Express it using Big O notation.

Common Recurrence Relations

Page 18 of 48
DAA 22CSE52

Algorithm Recurrence Relation

Factorial T(n) = T(n-1) + O(1)

Fibonacci T(n) = T(n-1) + T(n-2) + O(1)

Merge Sort T(n) = 2T(n/2) + O(n)

Binary Search T(n) = T(n/2) + O(1)

Example 1 – Factorial

Algorithm:

factorial(n):
if n == 0 or n == 1
return 1
else
return n * factorial(n-1)
Recurrence Relation
T(n) = T(n-1) + O(1)

Solution

T(n) = T(n-1) + 1
= T(n-2) + 1 + 1
= T(n-3) + 1 + 1 + 1
...
= T(1) + (n-1) × 1
= 1 + (n-1)
= O(n)

Time complexity → O(n)

Page 19 of 48
DAA 22CSE52

Example 2 – Fibonacci Sequence

Algorithm:

fibonacci(n):
if n == 0 or n == 1
return n
else
return fibonacci(n-1) + fibonacci(n-2)

✅ Recurrence Relation

T(n) = T(n-1) + T(n-2) + O(1)

Solution

This is a complex recurrence with exponential growth.

The solution is O(2ⁿ), because it branches into two calls at each step.

Time complexity → O(2ⁿ)

Page 20 of 48
DAA 22CSE52

Example 3 – Merge Sort

Algorithm:

mergeSort(arr, start, end):

if start < end
mid = (start + end) // 2
mergeSort(arr, start, mid)
mergeSort(arr, mid+1, end)
merge(arr, start, mid, end)

✅ Recurrence Relation

T(n) = 2T(n/2) + O(n)

✅ Solution Using Recursion Tree

• Level 0 → O(n)
• Level 1 → 2 × O(n/2) = O(n)
• Level 2 → 4 × O(n/4) = O(n)
• Level log n → O(n)

Total work → O(n log n)

Page 21 of 48
DAA 22CSE52

✅ Methods for Solving Recurrence Relations

1. Substitution Method

• Guess the solution.

• Prove it by induction.

Example: Guess that T(n) = O(n log n) for merge sort.

2. Recursion Tree Method

• Draw the recursive calls as a tree.

• Add work done at each level.
• Sum the work across levels.

Example: For merge sort → all levels have work O(n), and log n levels → O(n log n).

✅ 3. Master Theorem

Used for divide-and-conquer recurrences of the form:

T(n) = aT(n/b) + f(n)

Where:

• a = number of recursive calls

• b = input size division factor
• f(n) = work done at each level

Apply cases based on comparison between f(n) and n^(log_b a).

Page 22 of 48
DAA 22CSE52

✅ Space Complexity Analysis

✔ Each recursive call uses stack space

✔ Space = O(depth of recursion)

Example:

• Factorial → O(n) space

• Fibonacci → O(n) space (if not optimized)
• Merge sort → O(log n) auxiliary space due to recursion depth

Page 23 of 48
DAA 22CSE52

1. Practice Problems with Recurrence Relation Derivations

➤ Problem 1 – Factorial

Algorithm:

factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n-1)

Recurrence Relation:

T(n) = T(n-1) + O(1)

Base Case:

T(1) = O(1)

Solution:

T(n) = T(n-1) + 1
= T(n-2) + 1 + 1
= ...
= T(1) + (n-1)
= O(n)

Page 24 of 48
DAA 22CSE52

➤ Problem 2 – Fibonacci

Algorithm:

fibonacci(n):
if n == 0 or n == 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)

Recurrence Relation:

T(n) = T(n-1) + T(n-2) + O(1)

Base Case:

T(1) = O(1)

Solution (Observation):
It expands like a binary tree → grows exponentially → O(2ⁿ)

➤ Problem 3 – Merge Sort

Algorithm:

mergeSort(arr, start, end):

if start < end:
mid = (start + end) // 2
mergeSort(arr, start, mid)
mergeSort(arr, mid+1, end)
merge(arr, start, mid, end)

Page 25 of 48
DAA 22CSE52

Recurrence Relation:

T(n) = 2T(n/2) + O(n)

Base Case:

T(1) = O(1)

Solution Using Recursion Tree:

• Level 0 → O(n)
• Level 1 → 2 × O(n/2) = O(n)
• Level 2 → 4 × O(n/4) = O(n)
• ...
• Level log n → O(n)

Total Work → O(n log n)

2. Examples Solved Using Substitution Method

➤ Example – Solve T(n) = 2T(n/2) + n

Step 1: Guess that T(n) = O(n log n)

Step 2: Apply substitution:

T(n) = 2T(n/2) + n
= 2 [ (n/2) log(n/2) ] + n
= n log(n/2) + n
= n (log n − log 2) + n
= n log n − n + n

Page 26 of 48
DAA 22CSE52

= n log n

Result:
T(n) = O(n log n)

➤ Example – Solve T(n) = T(n-1) + n

Step 1: Expand

T(n) = T(n-1) + n
= T(n-2) + (n-1) + n
= T(n-3) + (n-2) + (n-1) + n
...
= T(1) + 2 + 3 + ... + n

Step 2: Use formula for sum of first n numbers

= O(1) + (n(n+1)/2 − 1)
= O(n²)

Result:
T(n) = O(n²)

✅ 3. Examples Solved Using Recursion Tree Method

➤ Example – T(n) = 3T(n/3) + n

Recursion Tree:

• Level 0 → O(n)
• Level 1 → 3 × O(n/3) = O(n)
• Level 2 → 9 × O(n/9) = O(n)
• ...
Page 27 of 48
DAA 22CSE52

• Level log₃ n → O(n)

Total work = log₃ n levels × O(n) = O(n log n)

➤ Example – T(n) = T(n/2) + O(1)

Recursion Tree:

• Level 0 → O(1)
• Level 1 → O(1)
• Level 2 → O(1)
• ...
• Level log₂ n → O(1)

Total work = O(log n)

4. Python Implementation of Recursive Algorithms with Memoization

➤ Example – Fibonacci Using Memoization

def fibonacci(n, memo={}):

if n in memo:
return memo[n]
if n == 0 or n == 1:
return n
memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
return memo[n]

# Example Usage
n = 50
print(f"Fibonacci({n}) =", fibonacci(n))

Page 28 of 48
DAA 22CSE52

Time Complexity

✔ Without memoization → O(2ⁿ)

✔ With memoization → O(n) Space Complexity

✔ O(n), as it stores results for each value from 0 to n

➤ Another Example – Factorial with Memoization

def factorial(n, memo={}):

if n in memo:
return memo[n]
if n == 0 or n == 1:
return 1
memo[n] = n * factorial(n-1, memo)
return memo[n]

# Example Usage
n = 100
print(f"Factorial({n}) =", factorial(n))

✔ Recursion is powerful but can be inefficient without optimization

✔ Recurrence relations help in analyzing recursive problems

✔ Substitution and recursion tree methods are tools to solve these relations

✔ Memoization optimizes recursive algorithms by storing previously computed results

✔ Python makes it easy to implement recursion with memoization using dictionaries

Page 29 of 48
DAA 22CSE52

Additional Practice Problems with Recurrence Relations

Problem 4 – Tower of Hanoi

Algorithm:
Move n disks from source to destination using auxiliary rod.

tower_of_hanoi(n, source, destination, auxiliary):

if n == 1:
move disk from source to destination
else:
tower_of_hanoi(n-1, source, auxiliary, destination)
move disk from source to destination
tower_of_hanoi(n-1, auxiliary, destination, source)

Recurrence Relation:

T(n) = 2T(n-1) + O(1)

Base Case:

T(1) = O(1)

Solution:

T(n) = 2(2T(n-2) + 1) + 1
= 4T(n-2) + 3
= 4(2T(n-3) + 1) + 3
= 8T(n-3) + 7
= ...
= 2ⁿ − 1

Page 30 of 48
DAA 22CSE52

Time Complexity → O(2ⁿ)

Problem 5 – Binary Search

Algorithm:
Search for a value in a sorted array.

binary_search(arr, low, high, x):

if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid-1, x)
else:
return binary_search(arr, mid+1, high, x)

Recurrence Relation:

T(n) = T(n/2) + O(1)

Base Case:

T(1) = O(1)

Solution:

Total levels = log₂ n

Time Complexity = O(log n)

Page 31 of 48
DAA 22CSE52

➤ Problem 6 – Exponentiation

Algorithm:
Compute xⁿ.

power(x, n):
if n == 0:
return 1
if n is even:
return power(x, n/2) * power(x, n/2)
else:
return x * power(x, n-1)

Recurrence Relation:

T(n) = T(n/2) + O(1)

Base Case:

T(0) = O(1)

Solution:

T(n) = O(log n)

✅ Python Implementation – Tower of Hanoi

def tower_of_hanoi(n, source, destination, auxiliary):

if n == 1:
print(f"Move disk 1 from {source} to {destination}")
return 1
count = 0

Page 32 of 48
DAA 22CSE52

count += tower_of_hanoi(n-1, source, auxiliary, destination)

print(f"Move disk {n} from {source} to {destination}")
count += 1
count += tower_of_hanoi(n-1, auxiliary, destination, source)
return count

# Example Usage
n=3
moves = tower_of_hanoi(n, 'A', 'C', 'B')
print(f"Total moves required: {moves}")

✅ Python Implementation – Binary Search

def binary_search(arr, low, high, x):

if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid-1, x)
else:
return binary_search(arr, mid+1, high, x)

# Example Usage
arr = [1, 3, 5, 7, 9, 11, 13]
x=7
result = binary_search(arr, 0, len(arr)-1, x)
if result != -1:

Page 33 of 48
DAA 22CSE52

print(f"Element {x} found at index {result}")

else:
print(f"Element {x} not found")

✅ Python Implementation – Power Function with Memoization

def power(x, n, memo={}):

if n in memo:
return memo[n]
if n == 0:
return 1
if n % 2 == 0:
half = power(x, n // 2, memo)
memo[n] = half * half
else:
memo[n] = x * power(x, n - 1, memo)
return memo[n]

# Example Usage
x=2
n = 10
print(f"{x}^{n} =", power(x, n))

✔ Recursive problems can be modeled using recurrence relations

✔ Substitution and recursion trees help in solving and analyzing complexity

✔ Tower of Hanoi gro]ws exponentially → O(2ⁿ)

✔ Binary search is highly efficient → O(log n)

Page 34 of 48
DAA 22CSE52

✔ Power function can be optimized using memoization → O(log n)

✔ Python’s dictionary structure makes memoization simple and effective

Non-Recursive Algorithms

Definition:
A non-recursive algorithm is an algorithm that solves problems without calling itself. It

relies on loops such as for, while, or other control structures to perform repetitive tasks.

✔ It solves problems through iteration rather than recursion.

✔ The problem is broken down into steps that are executed sequentially.

2. Characteristics of Non-Recursive Algorithms

✔ Uses loops like for, while, and do-while

✔ No stack frames for recursive calls

✔ Requires less memory compared to recursion

✔ Often faster and more efficient for simple problems

✔ Easier to understand in basic problems

✔ Suitable where recursion is unnecessary or costly

3. Comparison – Recursive vs Non-Recursive

Feature Recursive Algorithm Non-Recursive Algorithm

Definition Calls itself Uses loops or iteration

Memory usage Uses stack frames Uses fixed memory

Efficiency Can be inefficient Often more efficient

Page 35 of 48
DAA 22CSE52

Feature Recursive Algorithm Non-Recursive Algorithm

Complexity May grow exponentially Usually linear or constant

Base case Required Not required

Readability Elegant for some problems Clear and straightforward

4. Common Non-Recursive Algorithms with Examples

Example 1 – Factorial

Problem: Compute the factorial of a number n.

def factorial(n):
result = 1
for i in range(1, n+1):
result *= i
return result

# Example
n=5
print(f"Factorial({n}) =", factorial(n))

✔ Time Complexity → O(n)

✔ Space Complexity → O(1)

Example 2 – Fibonacci Sequence

Problem: Find the nth Fibonacci number.

def fibonacci(n):
a, b = 0, 1

Page 36 of 48
DAA 22CSE52

for _ in range(n):
a, b = b, a + b
return a

# Example
n = 10
print(f"Fibonacci({n}) =", fibonacci(n))

✔ Time Complexity → O(n)

✔ Space Complexity → O(1)

✅ Example 3 – Binary Search

Problem: Search for an element in a sorted array.

def binary_search(arr, x):

low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
low = mid + 1
else:
high = mid - 1
return -1

# Example

Page 37 of 48
DAA 22CSE52

arr = [1, 3, 5, 7, 9, 11]

x=7
index = binary_search(arr, x)
if index != -1:
print(f"Element {x} found at index {index}")
else:
print(f"Element {x} not found")

✔ Time Complexity → O(log n)

✔ Space Complexity → O(1)

Example 4 – Prime Number Check

def is_prime(n):
if n <= 1:
return False
for i in range(2, int(n**0.5)+1):
if n % i == 0:
return False
return True

# Example
n = 29
print(f"{n} is prime:", is_prime(n))

✔ Time Complexity → O(√n)

✔ Space Complexity → O(1)

Example 5 – Sum of Array Elements

def array_sum(arr):

Page 38 of 48
DAA 22CSE52

total = 0
for num in arr:
total += num
return total

# Example
arr = [1, 2, 3, 4, 5]
print(f"Sum of array elements: {array_sum(arr)}")

✔ Time Complexity → O(n)

✔ Space Complexity → O(1)

✅ 5. Advantages of Non-Recursive Algorithms

✔ Saves memory by avoiding stack overhead

✔ Easier to debug for basic problems

✔ Often faster due to reduced function call overhead

✔ No need for base cases

✔ Suitable for problems where iterative thinking suffices

6. When to Use Non-Recursive Algorithms

✔ When the problem can be solved by simple loops

✔ When performance is critical and stack memory is limited

✔ For real-time systems where recursion might lead to stack overflow

✔ When readability and maintainability are priorities for small tasks

✅ 7. Time and Space Complexity Analysis

Page 39 of 48
DAA 22CSE52

Algorithm Time Complexity Space Complexity

Factorial O(n) O(1)

Fibonacci O(n) O(1)

Binary Search O(log n) O(1)

Prime Check O(√n) O(1)

Array Sum O(n) O(1)

Recursive Non-Recursive
Algorithm Notes
Version (Iterative) Version

Factorial Recursion Loop-based Good beginner example

Efficient iterative
Iterative with a loop or
Fibonacci Recursion approach avoids
array
repeated calls

Iterative with while

Binary Search Recursion Works on sorted arrays
loop

Non-recursive is Classic recursive

Tower of Hanoi Recursion
complex or uses stack problem
Tree Traversals
Using stack to simulate Good for learning data
(Inorder, Preorder, Recursion
recursion structures
Postorder)

GCD (Euclidean Easy to switch between

Recursion Loop-based
Algorithm) methods

Iterative version exists Used for sorting large

Merge Sort Recursion
but more complex datasets

Page 40 of 48
DAA 22CSE52

Recursive Non-Recursive
Algorithm Notes
Version (Iterative) Version

Depth First Search

Recursion Using stack Used in graph problems
(DFS)

Page 41 of 48
DAA 22CSE52

Recursive Problems

Example Use
# Problem Description Base Case
Case
Multiply n with Mathematical
1 Factorial (n!) factorial(0) = 1
factorial of n-1 computations
nth term is sum of fibonacci(0) = 0, Sequence
2 Fibonacci Series
previous two fibonacci(1) = 1 generation
Recursively search
3 Binary Search low > high → not found Efficient searching
sorted array
Move disks between
4 Tower of Hanoi n = 1 → move one disk Puzzle solving
rods recursively
GCD (Euclidean Find greatest common
5 b = 0 → return a Math problems
Algorithm) divisor
Sum of Array Sum elements by
6 n = 0 → return 0 Array calculations
Elements reducing size
Check if string reads
7 Palindrome Check start >= end → True String validation
same both ends
Swap ends and reverse String
8 String Reversal start >= end → return
inside manipulation
Calculate base^exp by Power
9 Exponentiation exp = 0 → return 1
recursive multiplication calculations
Combinations Pascal’s triangle Probability
10 r = 0 or n = r → 1
(nCr) identity problems
Count number of digits
11 Count Digits n = 0 → return 0 Digit operations
by dividing by 10
Find Largest Compare elements to
12 n = 1 → return arr[0] Array analysis
Element find max
Check Armstrong Sum of powered digits Special number
13 n = 0 → return 0
Number equals number checks
Explore paths Reached destination Game or AI
14 Maze Solving
recursively to find exit → return problems
Graph Traversal Visit nodes deeply via All neighbors visited Network
15
(DFS) neighbors → return exploration
Generate Swap and rearrange Reached end of
16 Combinatorics
Permutations elements arrangement → print
Out of bounds or
Flood Fill Fill connected cells
17 different color → Image processing
Algorithm recursively
return
Page 42 of 48
DAA 22CSE52

Example Use
# Problem Description Base Case
Case
Convert decimal to Number
18 Decimal to Binary n = 0 → return ""
binary conversion
Print Numbers 1 to Recursively print Learning
19 n = 0 → return
N sequence recursion flow
Tower of Hanoi Explore advanced Algorithm
20 n = 1 → move disk
Variants Hanoi puzzles optimization

Non Recursive Problems

Example Use
# Problem Description Iterative Approach
Case
Multiply numbers from Use a loop to Mathematical
1 Factorial (n!)
n down to 1 multiply calculations
Tower of Hanoi Simulate moves using Use iterative
2 Puzzle solving
(Iterative) stack or loop simulation
Generate terms by Use loop and Sequence
3 Fibonacci Series
adding previous two temporary variables generation
Sum of Array Sum all elements in Loop through
4 Array processing
Elements array elements
Use while loop with Efficient
5 Binary Search Search in sorted array
boundaries searching
Prime Number Verify if a number has
6 Loop from 2 to √n Math validations
Check divisors
GCD (Euclidean Find GCD using While loop until
7 Number theory
Algorithm) repeated division remainder is 0
LCM (Least Common Find LCM using formula Find using GCD or Fraction
8
Multiple) or loop search multiples operations
Check if string or
Two-pointer
9 Palindrome Check number reads same String analysis
scanning loop
both ways
Reverse characters in a
10 String Reversal Swap using loop Text processing
string

Page 43 of 48
DAA 22CSE52

Example Use
# Problem Description Iterative Approach
Case
Multiply repeatedly Power
11 Exponentiation Calculate base^exp
in loop calculations
Calculate using factorial Use iterative Probability
12 Combinations (nCr)
formula factorials problems
Count how many digits Divide by 10 in a
13 Count Digits Number analysis
in a number loop
Find Largest Identify maximum in Scan with loop and
14 Array operations
Element array compare
Check Armstrong Sum powered digits and Loop through digits Special number
15
Number compare and sum check
Visit all cells row-wise Image and data
16 Matrix Traversal Use nested loops
or column-wise processing
Use temporary
Array
17 Array Rotation Shift elements k steps storage or swap in
manipulation
loop
Sort array using simple Bubble sort,
18 Sorting Algorithms Data organization
methods selection sort
Decimal to Binary Convert number into Loop with division Number system
19
Conversion binary and remainder conversion
Print Numbers 1 to Print sequence of Learning iteration
20 Simple loop
N numbers flow

Page 44 of 48
DAA 22CSE52

Question Bank
1. Algorithm Introduction

1. Define an algorithm.
2. What are the characteristics of a good algorithm?
3. Explain the differences between algorithm and program with examples.
4. Why is it important to analyze an algorithm?
5. Write an algorithm to find the largest element in an array.
6. Explain flowchart representation of algorithms.

2. Fundamentals of Algorithmic Problem Solving

7. What are the steps involved in algorithmic problem solving?

8. Explain problem specification with examples.
9. How do you approach breaking down a problem into smaller sub-problems?
10. Write an algorithm to calculate the GCD of two numbers using the Euclidean
method.
11. Explain the importance of base cases in recursive algorithms.
12. Solve a problem by applying divide and conquer technique.

3. Asymptotic Notations

13. Define time complexity and space complexity.

14. What is Big O notation? Give examples.
15. Differentiate between Big O, Omega (Ω), and Theta (Θ) notations.
16. Explain how asymptotic analysis helps in comparing algorithms.
17. Write time complexity for the following algorithms:
o Linear search
o Binary search
o Merge sort
18. Explain why worst-case analysis is important.

4. Standard Notations and Common Functions

19. List commonly used functions and classify them by growth rate.

Page 45 of 48
DAA 22CSE52

20. Explain O(1), O(n), O(n²), O(log n), and O(n log n) with examples.
21. Write examples where O(1) time complexity applies.
22. Compare exponential and polynomial complexities.
23. Explain space complexity with an example algorithm.

5. Important Problem Types

24. Explain sorting problems and give examples.

25. What are searching problems? Write an example.
26. Explain mathematical problems that can be solved using recursion.
27. Differentiate between combinatorial and optimization problems with examples.
28. Solve a problem to check if a number is prime.
29. Explain real-world applications of algorithm problems.

6. String Processing Problems

30. Define string matching and searching problems.

31. Write an algorithm to check if a string is a palindrome.
32. Explain pattern matching using brute-force method.
33. Solve problems related to substring checking.
34. Write a program to count occurrences of a substring in a string.
35. Explain edit distance between two strings.

7. Graph Problems

36. Define a graph and explain different types of graphs.

37. Differentiate between directed and undirected graphs.
38. Explain breadth-first search (BFS) with an example.
39. Explain depth-first search (DFS) and write its algorithm.
40. Solve problems like finding shortest path or cycles in graphs.
41. What are adjacency matrix and adjacency list representations?

8. Combinatorial Problems

42. Define permutations and combinations.

Page 46 of 48
DAA 22CSE52

43. Write an algorithm to generate all subsets of a set.

44. Solve problems like n-queens or traveling salesman problem.
45. Explain how recursion helps in solving combinatorial problems.
46. Write code to calculate factorial recursively and iteratively.
47. Discuss problems involving counting and arrangement.

9. Recurrence – Substitution Method

48. Write the recurrence relation for merge sort.

49. Solve the recurrence T(n) = T(n-1) + n using the substitution method.
50. Explain how substitution helps in analyzing recursive problems.
51. Derive the recurrence relation for binary search.
52. Solve T(n) = 2T(n/2) + n using recursion tree method and substitution.
53. Differentiate between iterative and recursive approaches in solving problems.

10. Recursive Tree Method

54. Draw recursion trees for merge sort and binary search.
55. How does recursion tree help in determining time complexity?
56. Explain how to sum the cost at each level of a recursion tree.
57. Solve the recurrence T(n) = 3T(n/3) + n using recursion tree method.
58. Compare recursion tree method with substitution method.
59. Solve T(n) = T(n/2) + O(1) using recursion tree.

11. General Recursive and Algorithm Analysis Questions

60. Why is it necessary to analyze algorithms before implementation?

61. What is the role of mathematical analysis in algorithm design?
62. Explain the importance of base cases and termination in recursive algorithms.
63. Solve problems related to graphs, strings, and combinatorics by applying recursive
or iterative methods.

Page 47 of 48
DAA 22CSE52

Page 48 of 48