unit1
Uploaded by
deeppati800unit1
Uploaded by
deeppati800Introduction: Characteristics of algorithm.
Analysis of
algorithm: Asymptotic analysis of complexity bounds – best,
average and worst-case behavior; Performance
measurements of Algorithm, Time and space trade-offs,
Analysis of recursive algorithms through recurrence
relations:
Substitution method, Recursion tree method and Masters’
theorem
Here’s a clear and organized set of notes for your topic:
Introduction: Characteristics of Algorithm
An algorithm is a step-by-step finite sequence of well-defined instructions for solving a computational
problem.
Characteristics of a Good Algorithm:
1. Input: Should accept zero or more inputs.
2. Output: Should produce at least one output.
3. Definiteness: All instructions must be clear and unambiguous.
4. Finiteness: Must terminate after a finite number of steps.
5. Effectiveness: Each step must be basic enough to be performed exactly and in finite time.
6. Correctness: Must correctly solve the problem for all valid inputs.
Analysis of Algorithm
Goal: To predict the resources an algorithm needs (such as time and space) without implementing it.
Asymptotic Analysis
Asymptotic analysis describes the running time or space used by an algorithm in terms of input
size (n), when n becomes very large.
Focuses on order of growth (ignores constant factors and lower-order terms).
Expressed using:
Big O (O): Upper bound — worst-case.
Big Omega (Ω): Lower bound — best-case.
Big Theta (Θ): Tight bound — average-case or exact asymptotic behavior.
Types of Cases
Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 1/3
Best Case: Minimum time required for inputs.
Average Case: Expected time over all inputs.
Worst Case: Maximum time required for any input.
Performance Measurements of Algorithm
Time Complexity: Measures the amount of time an algorithm takes as a function of input size.
Space Complexity: Measures the amount of memory an algorithm uses relative to input size.
Time and Space Trade-offs
Sometimes, more memory can lead to faster execution, and vice versa.
Example: Storing computed values (Memoization) saves time but uses more space.
Designing an algorithm often requires balancing time efficiency and space efficiency based on
requirements.
Analysis of Recursive Algorithms Through Recurrence Relations
Recursive algorithms are analyzed using recurrence relations, which express the running time of
a problem in terms of the running time for smaller inputs.
Methods for Solving Recurrence Relations:
1. Substitution Method
Guess the form of the solution.
Prove the guess correct using mathematical induction.
Steps:
1. Assume T(n) ≤ f(n) for some function f(n).
2. Substitute in the recurrence and solve.
Example:
T(n) = 2T(n/2) + n
Guess: T(n) = O(n log n)
2. Recursion Tree Method
Expand the recurrence into a tree structure.
Sum the costs at each level.
Sum the costs across all levels.
Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 2/3
Example (for T(n) = 2T(n/2) + n):
Level 0 cost: n
Level 1 cost: 2 × (n/2) = n
Level 2 cost: 4 × (n/4) = n
… continues for log n levels.
Total cost: n log n.
3. Master’s Theorem
Provides a direct way to find asymptotic behavior for recurrences of the form:
n
T (n) = aT ( ) + f (n)
b
Where:
a ≥ 1 and b > 1 are constants,
f (n) is an asymptotically positive function.
Master Theorem Cases:
Case 1: If f (n) = O(nlogb a−ϵ ) for some ϵ > 0,
T (n) = Θ(nlogb a )
Case 2: If f (n) = Θ(nlogb a logk n) for some k ≥ 0,
T (n) = Θ(nlogb a logk+1 n)
Case 3: If f (n) = Ω(nlogb a+ϵ ) for some ϵ > 0 and regularity condition holds,
T (n) = Θ(f (n))
Would you also like a short summarized diagram (cheat-sheet style) for this? It can help you revise
faster before exams! 📄
Printed using ChatGPT to PDF, powered by PDFCrowd HTML to PDF API. 3/3
