Unit 1: Complexity analysis and recursion
Design and Analysis of Algorithm notes · PTU syllabus (UGCC2519)
On this page
Unit summary
An algorithm is only useful if it is efficient. This unit teaches how to measure efficiency — time and space complexity with asymptotic notation — how to analyse common algorithms, and how to analyse recursive algorithms using recurrences and the Master theorem.
After this unit you can
- Define time and space complexity and use O, Ω and Θ
- Analyse sequential search, bubble, selection and insertion sort and matrix multiplication
- Write recurrences for recursive algorithms
- Solve recurrences using the Master theorem
PTU syllabus topics
- Design and performance analysis of algorithms
- time and space complexity
- asymptotic notations (O, Ω, Θ)
- analysis of sequential search/bubble sort/selection sort/insertion sort/matrix multiplication
- recursion basics
- analysis of recursive algorithms
- Master's theorem
Case 1
f(n) smaller than n^(log_b a) → T(n) = Θ(n^(log_b a))
Case 2
f(n) equal to n^(log_b a) → T(n) = Θ(n^(log_b a) log n)
Case 3
f(n) larger → T(n) = Θ(f(n))
Merge sort example
T(n) = 2T(n/2) + n → Θ(n log n)
Topic 1
Design and performance analysis
An algorithm is a finite sequence of unambiguous steps that solves a problem. Designing one involves understanding the problem, choosing a strategy (divide and conquer, greedy, dynamic programming …), proving correctness and analysing efficiency.
- Time complexity: how the number of basic operations grows with input size n.
- Space complexity: how much extra memory is needed.
- Analysis is done for the best, average and worst cases.
Topic 2
Asymptotic notations
| Notation | Meaning | Read as |
|---|---|---|
| O(g(n)) | f(n) ≤ c·g(n) for large n | Upper bound (at most) |
| Ω(g(n)) | f(n) ≥ c·g(n) for large n | Lower bound (at least) |
| Θ(g(n)) | Both O and Ω | Tight bound (exactly) |
Growth order: 1 < log n < n < n log n < n² < n³ < 2ⁿ < n!
Example
f(n) = 3n² + 5n + 2 is Θ(n²): for large n the n² term dominates and constants are ignored.
Topic 3
Analysis of basic algorithms
| Algorithm | Best | Worst |
|---|---|---|
| Sequential (linear) search | O(1) | O(n) |
| Bubble sort | O(n) with a swap flag | O(n²) |
| Selection sort | O(n²) | O(n²) |
| Insertion sort | O(n) | O(n²) |
| Matrix multiplication (n × n) | O(n³) | O(n³) |
Exam tip
Count the number of times the innermost statement runs. Two nested loops each running n times usually mean O(n²).
Topic 4
Recursion and recurrence relations
A recursive algorithm's time is described by a recurrence relation.
- Factorial: T(n) = T(n − 1) + c → O(n)
- Binary search: T(n) = T(n/2) + c → O(log n)
- Merge sort: T(n) = 2T(n/2) + cn → O(n log n)
Recurrences can be solved by substitution, the recursion-tree method, or the Master theorem.
Topic 5
The Master theorem
For T(n) = a·T(n/b) + f(n), with a ≥ 1 and b > 1, compare f(n) with n^(log_b a):
Case 1
If f(n) = O(n^(log_b a − ε)), then T(n) = Θ(n^(log_b a))
Case 2
If f(n) = Θ(n^(log_b a)), then T(n) = Θ(n^(log_b a) log n)
Case 3
If f(n) = Ω(n^(log_b a + ε)) and regularity holds, then T(n) = Θ(f(n))
Example
Merge sort: a = 2, b = 2, n^(log₂2) = n and f(n) = n → Case 2 → Θ(n log n). Binary search: a = 1, b = 2, n⁰ = 1 and f(n) = 1 → Case 2 → Θ(log n).
Key terms
- Time complexity
- Growth of running time with input size
- Big-O
- Asymptotic upper bound
- Theta
- Asymptotic tight bound
- Recurrence relation
- An equation defining T(n) in terms of smaller inputs
- Master theorem
- A formula for solving divide-and-conquer recurrences
Quick revision
- O upper, Ω lower, Θ tight.
- Nested n-loops → O(n²); matrix multiply → O(n³).
- Merge sort T(n) = 2T(n/2) + n = Θ(n log n).
- Master theorem: compare f(n) with n^(log_b a).
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.Define time and space complexity.
- Q2.Differentiate between Big-O and Theta notation.
- Q3.What is the worst-case complexity of insertion sort?
- Q4.Write the recurrence for binary search.
- Q5.State the Master theorem.
Long-answer questions
- Q1.Explain asymptotic notations with graphs and examples.
- Q2.Analyse bubble, selection and insertion sort in the best and worst cases.
- Q3.Explain how recursive algorithms are analysed using recurrence relations.
- Q4.Solve T(n) = 2T(n/2) + n, T(n) = 4T(n/2) + n and T(n) = T(n/2) + 1 using the Master theorem.
Stuck on this unit?
Message SBS on WhatsApp for help with Design and Analysis of Algorithm, or to ask about studying BCA at Synetic.