---

📘 Algorithms: Analyzing Algorithms

1️⃣ Meaning of Algorithm Analysis

Analyzing an algorithm means evaluating its efficiency in terms of:

• Time (how fast it runs)
• Space (how much memory it uses)

The main goal is to compare algorithms and predict performance before actual implementation.

Algorithm analysis helps us choose the best algorithm for a given problem.

---

2️⃣ Why Do We Analyze Algorithms?

Algorithm analysis is required to:

• Measure efficiency
• Compare two or more algorithms
• Optimize execution time
• Optimize memory usage
• Predict behavior for large inputs

👉 Example:
Both Bubble Sort and Merge Sort sort data, but Merge Sort performs better for large inputs.

---

3️⃣ Types of Algorithm Analysis

🔹 1. A Priori Analysis

• Done before coding
• Uses theoretical concepts
• Independent of hardware and programming language
• Focuses on algorithm logic

📌 Example:

• Counting number of comparisons
• Estimating loop iterations

---

🔹 2. A Posteriori Analysis

• Done after coding
• Based on actual execution
• Depends on:
  • Machine
  • Compiler
  • Input data

📌 Example:

• Measuring running time using a stopwatch
• Memory usage during execution

---

4️⃣ Performance Criteria for Algorithm Analysis

🔹 1. Time Complexity

Time complexity indicates how execution time grows with input size (n).

It depends on:

• Number of statements
• Loops
• Nested loops
• Recursive calls

📌 Example:

for i = 1 to n
   print i

Time Complexity = O(n)

---

🔹 2. Space Complexity

Space complexity refers to total memory used by an algorithm.

It includes:

• Input space
• Auxiliary space (extra variables, arrays, recursion stack)

📌 Example:

• Iterative algorithm → less space
• Recursive algorithm → more space (stack memory)

---

5️⃣ Case Analysis of Algorithms

🔹 Best Case

• Minimum time required
• Most favorable input

📌 Example:

• Linear Search: element found at first position
• Time Complexity → O(1)

---

🔹 Average Case

• Expected time for random input
• Difficult to calculate

📌 Example:

• Linear Search → O(n)

---

🔹 Worst Case

• Maximum time required
• Most unfavorable input

📌 Example:

• Linear Search: element at last position
• Time Complexity → O(n)

👉 Worst-case analysis is most commonly used in exams.

---

6️⃣ Asymptotic Analysis

Asymptotic analysis studies algorithm performance for large input sizes.

It ignores:

• Constants
• Lower-order terms

🔹 Asymptotic Notations

1. Big-O Notation (O)

• Represents upper bound
• Worst-case complexity

📌 Example:

T(n) = 3n² + 5n + 10
O(n²)

---

2. Omega Notation (Ω)

• Represents lower bound
• Best-case complexity

📌 Example:

Ω(n)

---

3. Theta Notation (Θ)

• Represents tight bound
• Best and worst case are same

📌 Example:

Θ(n log n)

---

7️⃣ Steps to Analyze an Algorithm

1. Identify input size (n)
2. Count basic operations
3. Calculate total operations
4. Express complexity using asymptotic notation
5. Analyze time and space

---

8️⃣ Example: Algorithm Analysis

Linear Search Algorithm

for i = 1 to n
   if a[i] == key
      return i

Case	Time Complexity
Best	O(1)
Average	O(n)
Worst	O(n)

---

---

🔚 Conclusion

Analyzing algorithms helps in:

• Understanding performance
• Selecting optimal solutions
• Designing efficient programs

A good algorithm is not only correct but also efficient in time and space.

---