Analysis of Algorithms
A Conceptual and Simplified Guide
1. Divide and Conquer
What is it? It is like building a massive Lego castle. Instead of trying to build the
whole thing at once, you build the towers, the walls, and the gate separately (Divide).
Then, you put them all together (Conquer/Combine).
Analogy: Splitting a large task among a team of people and combining their work at the
end.
• Divide: Break the problem into smaller, bite-sized pieces.
• Conquer: Solve those tiny pieces (usually so small they are instantly solvable).
• Combine: Merge the small answers to get the final big answer.
Complexity: We find the time complexity using mathematical formulas called "Recurrence
Relations." If we split a problem in half, it looks like T(n) = 2T(n/2) + O(n).
2. Sorting Algorithms
Sorting is simply organizing data (like putting books in alphabetical order). Here is the conceptual
breakdown of the top 5 methods:
Merge Sort (The Team Player)
Concept: Divide the list in half again and again until every item is by itself. Then, pair them up
in order, merging them back into a fully sorted list.
Analogy: Two people sorting two halves of a deck of cards, then carefully interlacing their finished
halves into one perfect deck.
Quick Sort (The "Taller or Shorter" Method)
Concept: Pick one random person (the Pivot). Tell everyone shorter to stand on the left, and
everyone taller to stand on the right. Repeat this for the left and right groups.
Analogy: Organizing students in a line by picking a student and moving the rest based on height.
Insertion Sort (The Card Player)
Concept: Look at one item at a time and insert it into its correct place among the items you
have already sorted.
Analogy: Holding a hand of playing cards and picking up a new card, sliding it exactly where it
belongs in your hand.
Selection Sort (The Perfectionist)
Concept: Scan the entire unsorted list to find the absolute smallest item. Swap it into the very
first position. Then find the next smallest, and so on.
Analogy: Searching a messy room for the absolute smallest toy, putting it in a box, and repeating.
Bubble Sort (The Floater)
Concept: Go down the line comparing two items side-by-side. If they are out of order, swap
them. The largest items "bubble" up to the end of the list.
Analogy: Heavy rocks sinking to the bottom while light bubbles float to the top.
Algorithm Concept / Strategy Best Case Time Worst Case Time
Merge Sort Divide, sort, merge O(n log n) O(n log n)
Quick Sort Pick pivot, partition O(n log n) O(n²)
Insertion Sort Place in sorted portion O(n) O(n²)
Selection Sort Find minimum, swap O(n²) O(n²)
Bubble Sort Swap adjacent if wrong O(n) O(n²)
3. Searching Algorithms
Linear Search (The Exhaustive Search)
Concept: Check every single item, one by one, from start to finish until you find what you
need.
Analogy: Looking for a lost sock by checking every single drawer in your house.
Time: O(n) worst-case.
Binary Search (The Smart Search)
Concept: Works ONLY on sorted lists. Open the middle. Is your target bigger or smaller? If
smaller, throw away the right half. Repeat.
Analogy: Looking up "Monkey" in a dictionary. You open halfway (to "M"). If you hit "N", you know
to search the left half. You don't read page by page!
Time: O(log n) worst-case (extremely fast!).
4. Asymptotic Notations (Measuring Speed)
Asymptotic notations are simply a way to grade an algorithm based on how it behaves as the
amount of data gets massive.
• Big O (The Pessimist): The worst-case scenario. "This algorithm will take AT MOST this long."
• Big Omega (The Optimist): The best-case scenario. "This algorithm will take AT LEAST this
long."
• Big Theta (The Realist): The exact/average scenario. The tight bound when best and worst
cases match.
5. Recurrence Relations
A recurrence relation is a mathematical equation that describes an algorithm's speed by defining it
in terms of itself. For example, if a function calls itself twice, its speed formula will include its own
name multiplied by two.
6. Master Theorem
Concept: Solving Recurrence Relations by hand takes a lot of complicated algebra.
The Master Theorem is a "Cheat Code" formula.
It applies to forms like T(n) = aT(n/b) + f(n). You just plug the numbers a, b, and the function f(n) into
three specific rules (cases) to instantly get the Big-O notation.
7. Dynamic Programming
Concept: "Those who cannot remember the past are condemned to repeat it." Dynamic
Programming remembers past answers so it never calculates the same thing twice.
Analogy: If I ask you 1+1+1+1, you count and say 4. If I then add "+1" to the end, you don't
recount from the start. You just remember 4 and add 1 to get 5.
8. Greedy Approach
Concept: Making the best immediate choice right now, without worrying about the
future. It "greedily" takes the biggest piece of the pie available at this exact moment.
Analogy: Making change for $0.80. You grab the biggest coin first (a 50-cent piece), then a
quarter, then a nickel. You don't plan ahead, you just grab the biggest fit right now.