BIGO-P2

Count the steps

Practice 2 of 5Cost: Big-O and friends7 tests

Here is a function that counts its own steps:

def work(n):
    count = 0
    for i in range(n):
        for j in range(i, n):
            count += 1
    for k in range(n):
        count += 2
    return count

Write count_steps(n), which returns exactly what work(n) returns. Running the loops is far too slow for the large tests, so find a formula.

count_steps(0)    # 0
count_steps(1)    # 3
count_steps(3)    # 12

Limits

n is a whole number from 0 up to 10¹⁸ (a 1 followed by 18 zeros). Return an int.

Builds on BIGO-1 Counting steps and BIGO-2 Big-O, Ω and Θ.

Continue on a laptop

Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.

Need a hint?0 of 3 opened

Hint 1Nudge
Hint 2Approach Open hint 1 first
Hint 3Pseudocode Open hint 2 first
Worked solutionlast resort Opens after all 3 hints

Python waits for a wider screensolution.py

Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.

7 tests, not run yet

Test results
#	Test	Result
1	n = 0	Not run
2	n = 1	Not run
3	n = 3	Not run
4	n = 10	Not run
5	Whole-number answer	Not run
6	n = 1,000,000	Not run
7	n = 10¹⁸	Not run

Count the steps

The problem

Limits

Need a hint?0 of 3 opened