Big O Notation Deep Dive | The Skill That Gets You Hired

Introduction to Big O Notation [0:00]

• Big O notation answers how much slower code gets as input size increases, measuring performance scaling.
• It's crucial for interviews at tech companies to analyze time and space complexity.
• Big O describes the shape of growth, not exact execution time.

  "Bigo answers one question. As my input gets bigger, how much slower does my code get?"

Understanding Complexity Classes [1:28]

• Operations are counted, not seconds; basic operations like comparisons or array access are fundamental.
• O(1) constant time: The number of operations remains constant regardless of input size (e.g., accessing the first element of a list).
• O(n) linear time: Work grows directly with input size (e.g., finding the largest number in a list by iterating through it).
• Constants and lower-order terms are dropped in Big O analysis (e.g., O(2n) becomes O(n), O(n^2 + n) becomes O(n^2)).

  "The work grows directly with the input size. We call this O of N linear time."

O(1) Constant Time [3:11]

• Time stays the same regardless of input size.
• Examples include accessing a list element by position and dictionary lookups using hash tables.
• O(1) operations are key to making slow code fast, like using sets or dictionaries for O(1) lookups.

  "The lookup time is the same. Now, 01 operations are often the key to making slow code fast."

O(n) Linear Time [4:20]

• If input doubles, time roughly doubles.
• Example: Searching for a value in a list by checking each item sequentially.
• Common in interview problems where each element needs to be examined once (finding max, sum, count).

  "10 items mean up to 10 checks. 10,000 items mean up to 10,000 checks. That's linear growth."

O(n^2) Quadratic Time [5:34]

• Occurs with nested loops, where for each item in the outer loop, the inner loop runs through all items.
• Example: Printing every possible pair of items from a list.
• Growth is rapid; 10 items yield 100 pairs, 100 items yield 10,000 pairs.

  "For each of the n items in the outer loop, we do n operations in the inner loop. 10 items, 100 pairs."

O(log n) Logarithmic Time [6:46]

• Very fast, almost as good as constant time.
• Achieved by repeatedly halving the problem size, like searching in a sorted phone book.
• Binary search is a prime example: it divides the search space in half with each step.
• Works only on sorted data; 1 million items take about 20 steps.

  "Each step cuts your problem in half. Now, here's the code and this is called the popular binary search."

O(n log n) Linearithmic Time [8:45]

• Combines linear and logarithmic complexity.
• Typical for efficient sorting algorithms like merge sort or quick sort.
• Intuition: Dividing the problem (log n) and processing elements at each level (n).
• Sits between linear and quadratic on a graph; efficient for most real-world applications.

  "The intuition is efficient sorting algorithms like merge sort or quick sort divide the problem into smaller pieces."

O(2^n) Exponential Time [10:00]

• Grows extremely fast.
• Example: Generating all possible subsets of a list, where each item has two choices (include or exclude).
• 10 items yield 1,024 subsets; 20 items yield over 1 million.
• Often appears in problems involving combinations or possibilities.

  "Each item has two choices. It's either in a subset or it's not. Two choices per items mean 2 * 2 * 2 n times."

O(n!) Factorial Time [11:17]

• The slowest complexity discussed.
• Involves permutations or orderings of a list.
• Example: Generating every possible ordering of a list.
• Grows faster than exponential; 10 items yield 3.6 million orderings.
• Usually indicates that finding an exact answer doesn't scale for larger inputs.

  "For the first position, we have n choices. For the second position, we have n minus one remaining choices."

Complexity Classes Comparison [12:30]

• Fastest to slowest: O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n), O(n!).
• The first four are generally acceptable for production code; the last two usually only work for small inputs.

  "The first four are generally acceptable for production code; the last two are warning size."

Framework for Analyzing Big O [13:10]

• Step 1: Identify the input that grows (e.g., list size n).
• Step 2: Find loops; nested loops multiply complexity (O(n^2)), sequential loops add (O(n) + O(n) = O(n)).
• Step 3: Look for halving (O(log n)), common in binary search or problems where the size is divided by two.
• Step 4: Check for hidden operations within loops (e.g., checking membership in a list can be O(m)).
• Step 5: Know built-in function costs (e.g., set lookups are O(1)).
• Step 6: Handle recursion by considering call count and work per call.

  "Loops are where work multiplies. This is usually where you start."

Tricky Problem 1: String Concatenation [14:55]

• Common mistake: Assuming O(n) for string concatenation in a loop.
• Reality: O(n^2) because strings are immutable in Python, requiring new string creation and copying on each concatenation.
• Fix: Collect string parts in a list (O(1) append) and join at the end (O(n)).

  "The common mistake most people look at this and say one loop O of N. The reality this is actually O of N square."

Tricky Problem 2: Nested Loops Not Always N^2 [16:10]

• Nested loops don't always mean O(n^2) if the inner loop's bounds are not dependent on n.
• Example: Inner loop runs a fixed number of times (e.g., 10), making the total complexity O(n * 10) = O(n).

  "The inner loop doesn't always run n times... The inner loop now runs at most 10 times regardless of how big n is."

Tricky Problem 3: Recursive Fibonacci [17:00]

• Naive recursive Fibonacci is O(2^n) due to repeated calculations of the same values.
• Drawing the call tree shows exponential growth.
• Fix: Use memoization (storing results) or dynamic programming to achieve O(n) time complexity.

  "Notice something. We are calculating fib of three twice. We are calculating fib of two multiple times."

Tricky Problem 4: Loop with Changing Increment [18:30]

• A loop where the variable doubles or halves each iteration is O(log n), not O(n).
• Example: i = 1; while i < n: i *= 2 runs log n times.

  "How many times can you double one before you reach or pass N. That's the definition of login."

Tricky Problem 5: Multiple Inputs [19:15]

• If a function takes multiple inputs (e.g., lists of size n and m), complexity should be expressed using both variables (O(n*m)).
• Avoid assuming inputs are the same size unless explicitly stated.

  "If list one has N items and list two has M items, this is O of N * M."

Interview Problem: Two Sum [20:00]

• Brute force solution: Check every pair, O(n^2) time, O(1) space.
• Good solution: Use a hash set (or dictionary) to store seen numbers. For each number, check if its complement exists in the set. This is O(n) time and O(n) space.
• The optimized approach is significantly faster for large inputs.

  "For each number, I know exactly what I need. Target minus that number. Now let me walk you through this solution."

Conclusion and Practice [22:30]

• Recap of Big O concepts, complexity classes, analysis framework, and tricky problems.
• For beginners, focus on recognizing patterns: one loop O(n), nested loops O(n^2), halving O(log n).
• Practice analyzing code to make Big O analysis natural.

  "The more you practice, the more natural it becomes."