Big-O Practice Questions I

This lesson focuses on applying Big-O notation to common loop patterns, with an emphasis on understanding the reasoning rather than just finding answers. Instead of guessing, we analyze code by counting how many times the main operation runs, then simplify it to determine how performance scales.

This section covers common patterns such as single loops, nested loops, sequential loops, constant time inner loops, and loops with increasing iteration counts. These patterns provide a foundation for analyzing algorithm efficiency.

Question 1: Loop with step size

This question analyzes a loop that increments by more than 1. It focuses on how step size impacts the number of iterations.

Explanation

This loop does not increase by 1 like a normal loop. Instead, it increases by 2 at each step.

So the values of i will be:

The loop continues until it reaches n. This means the total number of iterations is approximately:

Now we write the total work:

Big-O

Big-O notation ignores constant factors like $\frac{1}{2}$. Even though the loop runs fewer times than a standard loop, it still grows linearly with $n$.

Question 2: Reverse loop

This question examines a loop that runs in reverse order. It highlights that loop direction does not change the total iterations.

Explanation

This loop runs in reverse, starting from $n$ and decreasing to $1$ ...