Problem of the Day

Thursday, May 28, 2026

Problem:

Consider the following code segment, in which the greeting "Hello, world!" is printed a number of times that varies as a function on n.

for (int n = 0; n < 10; n++)
    for (int i = 0; i < (Math.pow(2, n)); i++)
        System.out.println("Hello, world!");

What is the Big-O performance of this segment?

O(1) - constant
O(n) - linear
O(n log n) - log linear
O(n²) - quadratic
O(2ⁿ) - exponential

Show solution:

The correct answer is e. As n increases linearly, the inner i loop runs 2ⁿ times, so the number of "Hello, world!" outputs being printed is increasing at an exponential rate.