---

📘 Mathematical Analysis of Recursive and Non-Recursive Algorithms

1️⃣ Introduction

Mathematical analysis of algorithms involves expressing the time and space requirements of an algorithm using mathematical functions based on the input size (n).

Algorithms are broadly classified as:

• Non-recursive (Iterative) algorithms
• Recursive algorithms

Each requires a different approach for mathematical analysis.

---

2️⃣ Mathematical Analysis of Non-Recursive Algorithms

🔹 Definition

A non-recursive algorithm uses loops (for, while) instead of recursive function calls.

The time complexity is analyzed by:

• Counting number of loop iterations
• Identifying the basic operation
• Expressing the count as a function of n

---

🔹 Steps for Analysis

1. Identify the basic operation
2. Count how many times it executes
3. Write a mathematical expression
4. Simplify using asymptotic notation

---

🔹 Example 1: Single Loop

for i = 1 to n
   print i

🔸 Mathematical Analysis

• Loop runs n times
• Basic operation executes n times

[
T(n) = n
]

👉 Time Complexity = O(n)

---

🔹 Example 2: Nested Loops

for i = 1 to n
   for j = 1 to n
      print i, j

🔸 Mathematical Analysis

• Inner loop runs n times
• Outer loop runs n times

[
T(n) = n \times n = n^2
]

👉 Time Complexity = O(n²)

---

🔹 Example 3: Loop with Variable Range

for i = 1 to n
   for j = 1 to i
      print j

🔸 Mathematical Analysis

[
T(n) = 1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}
]

👉 Time Complexity = O(n²)

---

3️⃣ Mathematical Analysis of Recursive Algorithms

🔹 Definition

A recursive algorithm solves a problem by calling itself with smaller input sizes.

Its analysis is done using recurrence relations.

---

4️⃣ Recurrence Relation

🔹 Definition

A recurrence relation expresses the time complexity of a recursive algorithm in terms of its complexity for smaller inputs.

📌 General Form:
[
T(n) = aT(n/b) + f(n)
]

Where:

• a = number of recursive calls
• n/b = size of subproblem
• f(n) = work done outside recursion

---

5️⃣ Example 1: Linear Recursion

Factorial Algorithm

factorial(n)
   if n == 0 return 1
   return n * factorial(n-1)

🔸 Recurrence Relation

[
T(n) = T(n-1) + c
]

🔸 Solution

[
T(n) = T(0) + nc = O(n)
]

---

6️⃣ Example 2: Binary Recursion

Fibonacci Algorithm (Naive)

fib(n)
   if n ≤ 1 return n
   return fib(n-1) + fib(n-2)

🔸 Recurrence Relation

[
T(n) = T(n-1) + T(n-2) + c
]

🔸 Solution

[
T(n) = O(2^n)
]

---

7️⃣ Example 3: Divide and Conquer

Binary Search

[
T(n) = T(n/2) + c
]

🔸 Solution

[
T(n) = O(\log n)
]

---

Merge Sort

[
T(n) = 2T(n/2) + cn
]

🔸 Solution (Master Theorem)

[
T(n) = O(n \log n)
]

---

8️⃣ Comparison: Recursive vs Non-Recursive Analysis

Aspect	Non-Recursive	Recursive
Method	Loop counting	Recurrence relations
Complexity Expression	Direct formula	Recursive formula
Space Usage	Less	More (stack)
Analysis Difficulty	Easier	More complex

---

9️⃣ Space Complexity Consideration

🔹 Non-Recursive

• Usually O(1) auxiliary space

🔹 Recursive

• Stack space depends on recursion depth
• Example: Factorial → O(n) space

---

🔟 Exam-Oriented Key Points

• Loop-based algorithms → count iterations
• Recursive algorithms → write recurrence relation
• Solve recurrence using substitution or Master Theorem
• Worst case is generally preferred

---

🔚 Conclusion

Mathematical analysis provides a systematic method to evaluate both recursive and non-recursive algorithms.

Iterative algorithms are easier to analyze, while recursive algorithms require recurrence relations for accurate complexity estimation.

---