Big O Notation - potatoscript/dsa GitHub Wiki

🧠 What is Big O?

Big O Notation is a way to measure how fast or how much memory a program uses as the input grows.

Think of it like this:

📦 "If I add more boxes to my room, how much longer will it take me to clean it?"

---

📦 Real-Life Example: Candy Sorting 🍬

Imagine you have a box of candies to sort:

Number of Candies	Time Needed
5	🕐 Short
500	🕐🕐🕐🕐🕐 Long
500,000	😵 Way too long!

Big O helps us predict how bad things will get as the number of candies (input size n) increases.

---

📊 Why Do Programmers Use Big O?

To answer questions like:

• Will this app slow down if there are more users? 🧍🧍🧍🧍
• Will this function still be fast with 1,000,000 items? 🧠
• Which algorithm is faster or more efficient? 🏎️ vs 🚲

---

🧰 Big O Common Types (With Cute Emoji Guides!)

Big O	Name	Speed	Emoji Metaphor
O(1)	Constant Time	⚡ Super Fast	Always same speed
O(log n)	Logarithmic	📚 Smart Fast	Skips chunks
O(n)	Linear	🚶 Normal	Step-by-step
O(n log n)	Log-Linear	🚴 Decent	Mix of linear + smart
O(n²)	Quadratic	🐌 Slow	Loops inside loops
O(2ⁿ)	Exponential	🐢🐢 Very Slow	Grows like crazy
O(n!)	Factorial	🦥 Max Slow	Tries everything

---

🍪 O(1): Constant Time

"No matter how many cookies 🍪 you have, I’ll grab one in 1 second!"

int firstItem = items[0];

✅ Accessing a specific index in an array.

📦 5 items? 1 second.
📦 5 million items? Still 1 second.

---

📚 O(log n): Logarithmic Time

"I'm reading a book 📖, but instead of every page, I skip half each time."

Binary Search is like this:

int binarySearch(int[] arr, int target)
{
    // Keep cutting the list in half
}

With 1,000 items, log₂(1000) ≈ 10 steps!

⚡ VERY efficient for big data!

---

🚶 O(n): Linear Time

"I check each student’s name in the list."

for (int i = 0; i < n; i++) {
    Console.WriteLine(names[i]);
}

⏱️ Time grows step-by-step with size.

---

🚴 O(n log n): Log-Linear Time

"Like a smart robot scanning rows 📊."

This is the speed of efficient sorting algorithms:

• Merge Sort
• Quick Sort (average case)

🧠 Mixes speed (log n) with checking every item (n)

---

🐌 O(n²): Quadratic Time

"Every student checks every other student."

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        Console.WriteLine(i + "," + j);
    }
}

🔁 Nested loops = performance sinks for big data.

Items	Time
10	100
100	10,000
1000	1,000,000 😰

---

🐢 O(2ⁿ): Exponential Time

Like doubling candy:

1 🍬 → 2 🍬 → 4 🍬 → 8 🍬 → ... 😱

Used in brute-force or recursive tree problems.

Example: calculating Fibonacci recursively:

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

Avoid this for big inputs!

---

🦥 O(n!): Factorial Time

"Try all combinations." Like arranging 5 books:

ABCDE  
ACBDE  
... (120 combinations)  

Used in:

• Puzzle solvers 🧩
• Permutations & brute-force

Too slow for anything more than 10 items. 🔥

---

🪄 Visual Comparison Chart

Here’s how the growth looks visually:

| Input Size (n) →   
|
|                         🦥  O(n!)
|                     🐢  O(2ⁿ)
|                🐌  O(n²)
|          🚴  O(n log n)
|     🚶  O(n)
|  📚  O(log n)
|⚡ O(1)
+---------------------------------

---

🧪 Real Code Examples (C#)

O(1)

int GetFirstItem(int[] arr)
{
    return arr[0]; // Always same time
}

O(n)

void PrintAllItems(int[] arr)
{
    foreach (var item in arr)
        Console.WriteLine(item); // n steps
}

O(n²)

void CompareAllPairs(int[] arr)
{
    for (int i = 0; i < arr.Length; i++)
        for (int j = 0; j < arr.Length; j++)
            Console.WriteLine(arr[i] + ", " + arr[j]);
}

---

🎈 Memory Complexity (Space)

Big O isn't just about speed! Also:

• 💾 How much space an algorithm uses
• 🧺 Temporary arrays, variables, etc.

Example:

int[] MakeCopy(int[] arr)
{
    int[] newArr = new int[arr.Length]; // O(n) space
    // ...
    return newArr;
}

---

🧠 Common Patterns Table

Code Pattern	Time Complexity
Single loop	O(n)
Nested loop	O(n²)
Divide in half (binary search)	O(log n)
Loop then divide	O(n log n)
Constant operations	O(1)

---

📦 Summary – You’ve Learned:

• Big O shows how time/space grows with input.
• Common types: O(1), O(n), O(n²), etc.
• Efficient code is better for large inputs!
• Choose the right algorithm, not just the correct one.

---