---

📘 Time Complexity (Detailed Discussion)

What is Time Complexity?

Time Complexity measures how much time an algorithm takes as a function of the input size (n).

👉 It tells us how fast an algorithm runs when the input grows.

It does not measure actual time (seconds, milliseconds).
Instead, it measures number of steps/operations an algorithm performs.

---

📌 Why Time Complexity is Important?

• Helps compare different algorithms
• Predicts performance for large inputs
• Helps choose the most efficient algorithm
• Avoids slow software systems
• Removes dependency on hardware speed

For example:

• Searching in a sorted list using Binary Search is much faster than Linear Search.
• Sorting using Merge Sort is more efficient than Bubble Sort.

---

📘 Types of Time Complexity

We analyze time complexity using:

1. Big-O Notation (O) → Worst Case

Upper bound
Example: “At most this much time”

2. Big-Ω (Omega) → Best Case

Lower bound
Example: “At least this fast”

3. Big-Θ (Theta) → Average/Tight Bound

Exact bound
Example: “On average, this time”

In most exams/interviews, Big-O is used.

---

📘 Common Time Complexities (with examples)

1. Constant Time — O(1)

Time does not depend on input size.

Examples:

• Accessing array element by index
• Pushing/popping from stack
• Checking if a number is even

---

2. Logarithmic Time — O(log n)

Time grows slowly even for large input.

Examples:

• Binary Search
• Height of balanced BST
• Divide and Conquer algorithms

👉 Input size halves at each step.

---

3. Linear Time — O(n)

Time grows proportionally to the input size.

Examples:

• Linear Search
• Finding maximum/minimum in an array
• Traversing a list

---

4. Linearithmic Time — O(n log n)

Combination of linear and logarithmic.

Examples:

• Merge Sort
• Heap Sort
• Quick Sort (average)

Most efficient sorting algorithms use O(n log n).

---

5. Quadratic Time — O(n²)

Time increases rapidly as input grows.

Examples:

• Bubble Sort
• Selection Sort
• Insertion Sort (worst case)
• Nested loops (i inside j)

---

6. Cubic Time — O(n³)

Triple nested loops.

Example:

• Matrix multiplication (brute force)

---

7. Exponential Time — O(2ⁿ)

Very slow — grows extremely fast.

Examples:

• Fibonacci (recursive)
• Subset generation
• Tower of Hanoi

---

8. Factorial Time — O(n!)

Used in brute-force permutation problems.

Examples:

• Traveling Salesman Problem (TSP) brute force
• Generating all permutations

---

📘 Time Complexity Table (most important)

Complexity	Name	Example
O(1)	Constant	Access array element
O(log n)	Logarithmic	Binary Search
O(n)	Linear	Linear Search
O(n log n)	Linearithmic	Merge Sort
O(n²)	Quadratic	Bubble Sort
O(n³)	Cubic	Matrix operations
O(2ⁿ)	Exponential	Fibonacci (recursion)
O(n!)	Factorial	TSP permutations

---

📌 How to Calculate Time Complexity (Rules)

Rule 1: Drop constants

O(2n) → O(n)
O(100) → O(1)

Rule 2: Consider the highest order term

O(n³ + n² + n + 5) → O(n³)

Rule 3: For loops

• Single loop → O(n)
• Nested loops → O(n²)
• Loop that divides n → O(log n)

Rule 4: Consecutive statements

Take the maximum, not the sum.

O(n) + O(n²) = O(n²)

Rule 5: Recursive algorithms

Use recurrence relations
E.g., Merge Sort: T(n) = 2T(n/2) + n → O(n log n)

---

📘 Examples of Calculating Time Complexity

Example 1:

for (i = 0; i < n; i++)
   cout << i;

Complexity → O(n)

---

Example 2:

for(i=0; i<n; i++)
   for(j=0; j<n; j++)
      cout<<i+j;

Complexity → O(n²)

---

Example 3:

while (n > 1)
   n = n / 2;

Complexity → O(log n)

---

Example 4:

cout << "Hello";

Complexity → O(1)

---

📌 Best, Worst, and Average Case Example

Consider Linear Search:

• Best Case (Ω(1)): item found at the first position
• Worst Case (O(n)): item not found or last position
• Average Case (Θ(n)): item is somewhere in the middle

---

📘 Graphical Comparison (Understanding Growth)

Fastest → Slowest:

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

---

🎯 Summary (Exam-Oriented)

• Time Complexity measures performance of an algorithm.
• Uses Big-O to express worst-case performance.
• Most common complexities: O(1), O(log n), O(n), O(n²), O(n log n).
• Nested loops → often O(n²).
• Divide & Conquer → O(n log n).
• Recursion → use recurrence to find complexity.
• Efficiency becomes crucial as input size grows.

---