Logic problem 10 of 30

Count the loop

Logic
Easy

After this code runs, what is the exact value of count in terms of n, and what is the Big-O running time?

count = 0
for i in range(n):
    for j in range(i, n):
        count += 1

Show hint

When i = 0 the inner loop runs n times. When i = n - 1 it runs once. Add those up.

Show solution

count = n + (n − 1) + ... + 1 = n(n + 1) / 2.

That is about n²/2, and Big-O drops constant factors, so the running time is O(n²). Starting the inner loop at i halves the work but does not change the growth rate.

Want a problem like this every day? See today's problem and keep a streak going.