---

📘 Time and Space Complexity of an Algorithm

1️⃣ Introduction

The efficiency of an algorithm is measured mainly using two parameters:

1. Time Complexity – how much time an algorithm takes to execute
2. Space Complexity – how much memory an algorithm uses during execution

Both are analyzed with respect to input size (n) and are expressed using asymptotic notations such as O, Ω, and Θ.

---

2️⃣ Time Complexity

🔹 Definition

Time complexity is the function that describes the amount of time an algorithm takes to run as a function of the input size n.

It does not measure actual time in seconds, but rather counts the number of basic operations performed.

---

🔹 Factors Affecting Time Complexity

• Size of input (n)
• Number of loops
• Number of nested loops
• Conditional statements
• Recursive calls

---

3️⃣ Types of Time Complexity

🔹 Best Case

• Minimum time required
• Most favorable input

📌 Example:
Linear Search – element found at first position
Best Case = 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
• Most commonly used in exams

📌 Example:
Linear Search – element found at last position
Worst Case = O(n)

---

4️⃣ Time Complexity Analysis with Examples

🔹 Constant Time – O(1)

a = b + c

Execution time is constant.

---

🔹 Linear Time – O(n)

for i = 1 to n
   print i

---

🔹 Quadratic Time – O(n²)

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

---

🔹 Logarithmic Time – O(log n)

Binary Search

---

🔹 Linear Logarithmic – O(n log n)

Merge Sort

---

5️⃣ Space Complexity

🔹 Definition

Space complexity is the total amount of memory used by an algorithm during execution.

It includes:

1. Input space
2. Auxiliary space (extra space used by algorithm)

---

🔹 Components of Space Complexity

1. Input Space

Memory required to store input data.

📌 Example:

• Array of size n → O(n)

---

2. Auxiliary Space

Extra memory used by algorithm (variables, recursion stack, temp arrays).

📌 Example:

• Merge Sort uses extra array → O(n)

---

6️⃣ Space Complexity Examples

🔹 Constant Space – O(1)

int a, b, c;

---

🔹 Linear Space – O(n)

int arr[n];

---

🔹 Recursive Space

factorial(n)

• Stack space = O(n)

---

7️⃣ Comparison: Time vs Space Complexity

Feature	Time Complexity	Space Complexity
Focus	Execution speed	Memory usage
Measured in	Operations	Memory units
Goal	Faster algorithm	Memory-efficient algorithm

---

8️⃣ Trade-off Between Time and Space

Sometimes:

• Faster algorithms use more memory
• Memory-efficient algorithms take more time

📌 Example:

• Using hashing increases space but reduces time

---

9️⃣ Importance in Algorithm Design

• Helps choose optimal algorithm
• Improves program efficiency
• Critical for large data processing
• Foundation for advanced techniques (DP, Greedy, D&C)

---

🔟 Exam-Oriented Key Points

• Worst-case time complexity is preferred
• Constants are ignored
• Space complexity includes recursion stack
• Always express complexity using Big-O notation

---

🔚 Conclusion

Time and space complexity analysis allows us to evaluate algorithm performance and choose the most efficient solution.

An efficient algorithm balances both time and space.

---