---

📘 Probabilistic Analysis (Introduction)

Probabilistic Analysis is a method of analyzing algorithms in which the input is assumed to be random, and the performance of the algorithm is calculated as the expected value.

👉 It gives Expected Time Complexity instead of Worst-Case Complexity.

---

📌 Why Probabilistic Analysis?

Many algorithms:

• Perform poorly only for rare or specific inputs
• But perform well for most inputs

Worst-case time complexity may not represent typical behavior.

Examples:

• Quick Sort worst-case → O(n²)
• But average case (expected) → O(n log n)
  Because probabilistic analysis assumes inputs are random.

---

📘 Deterministic vs Probabilistic Analysis

Deterministic Analysis	Probabilistic Analysis
Assumes worst or best case input	Assumes input follows a probability distribution
Gives worst-case or best-case	Gives expected (average) running time
Used for guaranteed performance	Used for realistic performance
Example: Worst-case of Quick Sort	Expected case of Quick Sort

---

📘 Where is Probabilistic Analysis Used?

1. Average-case analysis of algorithms
2. Hashing / Hash Tables
3. Randomized algorithms
4. Quick Sort & Quick Select
5. Skip Lists
6. Probabilistic Counting Algorithms
7. Load Balancing Algorithms
8. Random Input Models

---

📘 Example: Quick Sort (Classic Example)

For Quick Sort:

Worst Case: O(n²)
Expected / Probabilistic Case: O(n log n)

Why?

Because:

• Probability of selecting a bad pivot = very low
• Probability of partition creating balanced subproblems = high

Thus, using probability theory:

• Expected height of recursion tree = log n
• Expected work per level = n

👉 Expected Time = n × log n

---

📘 Example: Hashing

In a hash table:

• Worst-case search time = O(n)
• Expected search time = O(1) if each key has equal probability of being hashed to any slot.

Probability theory tells us:

• Expected number of collisions is small
• Expected chain length = load factor α = n/m

Thus operations (search, insert, delete) are expected O(1).

---

📘 Example: Randomized Algorithm Analysis

Some algorithms use randomness inside them.

Examples:

• Randomized Quick Sort
• Randomized Binary Search
• Randomized Selection Algorithms
• Monte Carlo and Las Vegas algorithms

We compute expected running time using probability of each random event.

---

📘 Formal Definition of Probabilistic Analysis

In probabilistic analysis:

• Define the probability distribution of all possible inputs
• Compute expected running time:

[
E[T(n)] = \sum_{i=1}^{k} P(input=i) \times Time(input=i)
]

Where:

• ( P(input=i) ) is the probability of the i-th input
• ( Time(input=i) ) is time taken for that input

---

📘 Types of Probabilistic Analysis

There are two types:

---

1. Distribution-based Probabilistic Analysis

Assumes inputs follow a known probability distribution.

Example:

• Every permutation of n elements is equally likely

Used in:

• Quick Sort
• Randomized Select

---

2. Randomized Algorithm Analysis

Algorithm itself makes random choices.

Example:

• Randomized pivot selection in Quick Sort
• Randomized skip lists
• Randomized hashing

---

📘 Example: Average Case of Linear Search

Problem:

Element is equally likely to be at any position in an array of size n.

Probability = 1/n for each index.

Expected time:

[
E[T] = \frac{1}{n}(1 + 2 + 3 + \dots + n)
= \frac{(n+1)}{2}
]

👉 Linear search average time = O(n)

---

📘 Key Points (For Exams)

• Probabilistic Analysis studies the expected behavior of algorithms.
• It uses probability theory to analyze average-case performance.
• Helps evaluate algorithms realistically for random inputs.
• Important in hashing, quicksort, randomized algorithms, load balancing, etc.
• Expected time often gives more practical understanding than worst-case.

---

🎯 Summary (Short Notes)

• Probabilistic Analysis = Expected running time analysis
• Uses probability of inputs or random choices
• Realistic: most important for algorithms like Quick Sort & Hashing
• Expected time often better than worst-case

---