Time Complexity and Big O Notation

# CHAPTER 2

Time Complexity and Big O Notation #

1. Introduction #

2. Learning Objectives #

• Define Time Complexity and Space Complexity.

• Understand and calculate Big O Notation mathematically.

• Differentiate between O(1), O(n), O(log n), and O(n²).

• Evaluate your own code to determine its efficiency.

3. What is Algorithm Analysis? #

1. 1. Time Complexity: How does the runtime of the algorithm increase as the size of the input data (n) grows?

1. 2. Space Complexity: How much extra RAM/Memory does the algorithm require as the input data (n) grows?

*Note: In modern computing, RAM is cheap, but CPU time is expensive. Therefore, Time Complexity is usually the primary focus in interviews.*

4. Big O Notation Explained #

We use the variable n to represent the size of the input (e.g., n = 1 million users).

#### 4.1 O(1) - Constant Time The algorithm takes the exact same amount of time to execute, regardless of whether n is 10 or 10 billion.

Real-world Analogy: Determining if a book's cover is red. It takes 1 second, whether the book has 10 pages or 10,000 pages.

// C Example: O(1)
int getFirstElement(int arr[]) {
    return arr[0]; // Instantaneous, regardless of array size!
}

#### 4.2 O(n) - Linear Time The runtime grows directly in proportion to the input size n. If you double the input, the time doubles.

Real-world Analogy: Reading every page of a book. A 500-page book takes 5 times longer to read than a 100-page book.

# Python Example: O(n)
def print_all_users(users_list):
    for user in users_list: # Loop runs 'n' times
        print(user)

#### 4.3 O(n²) - Quadratic Time (The Danger Zone) The runtime grows exponentially as the square of the input size. If the input is 10, it takes 100 operations. If the input is 1000, it takes 1,000,000 operations! *This happens when you nest loops.*

Real-world Analogy: Comparing every single book on a shelf to every other book on the shelf.

// Java Example: O(n²)
void printPairs(int[] arr) {
    for (int i = 0; i < arr.length; i++) {       // Runs n times
        for (int j = 0; j < arr.length; j++) {   // Runs n times for EACH outer loop
            System.out.println(arr[i] + ", " + arr[j]);
        }
    }
}

#### 4.4 O(log n) - Logarithmic Time (The Holy Grail) The runtime grows extremely slowly. Every time the input size doubles, the number of operations only increases by 1! This is achieved by dividing the problem in half on every step.

Real-world Analogy: Looking up a word in a dictionary. You don't read page 1, page 2, etc. You open the book exactly in the middle. If the word is earlier, you tear the book in half and look at the middle of the left half. You destroy half the remaining data on every step!

// C++ Example: O(log n) - Binary Search Concept
int binarySearch(int n) {
    int operations = 0;
    while (n > 1) {
        n = n / 2; // Data is cut in half every loop!
        operations++;
    }
    return operations;
}

5. Complexity Comparison Chart #

Let's visualize how many operations it takes if the input size n is 1,000:

6. Dropping Constants #

• O(2n) becomes O(n)

• O(n² + n + 500) becomes O(n²) (Because as n becomes 1 billion, the "+ 500" is statistically invisible).

7. Complexity Analysis #

// O(n) + O(n) = O(2n) -> O(n)
function processData(arr) {
    for(let i=0; i<arr.length; i++) { console.log(arr[i]); } // O(n)
    for(let i=0; i<arr.length; i++) { console.log(arr[i]); } // O(n)
}

Time Complexity: O(n). Space Complexity: O(1). (We did not create any new arrays or variables in memory).

8. Common Mistakes #

• Assuming nested loops are always O(n²): If the inner loop does not depend on n (e.g., it always loops exactly 5 times regardless of input size), the complexity is O(5n), which simplifies to O(n).

• Confusing Best, Average, and Worst Cases: Big O is strictly the *Worst Case*. Big Omega (Ω) is the Best Case. Big Theta (Θ) is the Average Case. Interviews almost exclusively care about Big O.

9. Best Practices #

• Never settle for O(n²) without trying for O(n log n) or O(n): If you write a nested loop in an interview, immediately stop and ask yourself: "Can I use a Hash Map to remove the inner loop?"

• Analyze Space as well as Time: Sometimes you can make an algorithm faster by caching data (using more Space). This is called the Time-Space Tradeoff.

10. Exercises #

1. 1. Simplify O(3n² + 4n + 1200).

1. 2. What is the time complexity of a loop that cuts the dataset in half on every iteration?

1. 3. If an array has 1 million elements, how many operations will an O(n) algorithm take?

11. MCQs with Answers #

12. Interview Preparation #

• *Conceptual:* Explain the difference between Time Complexity and Space Complexity. Provide an example of an algorithm that has O(n) Time Complexity but O(1) Space Complexity.

• *Conceptual:* Why do we drop constants and non-dominant terms in Big O Notation? Mathematically justify why O(n² + 1000n) simplifies to O(n²).

• *Whiteboard:* Analyze a block of code with three nested loops where the innermost loop only executes 5 times. What is the true Big O? *(Answer: O(n²) because the inner loop is constant).*

Common Pitfalls:

• Panicking when analyzing complex mathematical loops. Just remember: Count the loops. If they are nested and depend on n, multiply them. If they are sequential, add them.

13. FAQs #

14. Summary #

15. Next Chapter Recommendation #