Question

What is the f(n) runtime of the following pseudocode: sum = 0 for A = N/2 downto 1 for B = 1 to 4N increment sum by B

Answer 1

f(N) = 2+ N/2 + 6N² units of time.

Explanation:

Assigning 0 to the variable sum takes one unit of time.

Each time you increment sum by B, you need to call the value of sum, sum it to B and assign it to sum, which takes three units of time in total. You are repeating this process for each value of B which ranges from 1 to 4n and for each value of A which ranges from 1 to n/2. Opening the FOR takes also another unit of time, so, as a result, we have

f(N) 1 + 1 (open the FOR in A)+ N/2*(1 (open the FOR in B) + 4N*3) = 2+ N/2 + 6N² units of time. It has order complexity O(N²).