Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in C++

Big-O Practice Questions II

Explore advanced Big-O notation patterns by analyzing loops and recursive functions to understand how they affect algorithm efficiency. This lesson helps you interpret logarithmic, square root, exponential, and combined recursion-loop complexities, preparing you to evaluate algorithm scaling confidently.

We'll cover the following...

In this lesson, we’ll practice applying Big-O notation to more advanced patterns involving loops and recursion, focusing on how different growth rates impact time complexity. Instead of guessing, we analyze how many times operations run, especially in cases like logarithmic growth, shrinking inputs, and recursive calls.

We’ll explore patterns such as log-based loops, square root behavior, fast-growing loops, and different types of recursion. These concepts help develop a deeper understanding of algorithm efficiency and how algorithms scale with input size.

Question 1: Increasing inner loop (Log inside loop)

This question analyzes a loop where the inner loop grows exponentially. It focuses on how logarithmic behavior appears inside nested loops.

C++ 17
void multiplyByTwo(int n) {
    for (int i = 0; i < n; i++) {
        int j = 1;
        while (j < i) {
            j *= 2;
        }
    }
}

Explanation

The inner loop doubles j each time. So for a given ...