# Finding the worst case running time of this piece of code?

I am working with this code:

function strange (list a[0..n-1] of integers such that abs(a[i]) ≤ n for every 0 ≤ i ≤ n - 1, list b[0..2n] of zeroes)

for i ← 0 to n - 1 do
a[i] ← a[i] + n
for i ← 0 to n - 1 do
for j ← 0 to abs(a[i] - 1) do
b[j] ← b[j] + 1
return b


I am trying to figure out the worst running time for the code above and so far I'm guessing that the first for loop will run n times, but not sure how to prove this. For the second and third for loop, I'm unsure how to approach this. If possible, could someone help me solve this?

• How large can abs(a[i] - 1) be? – gnasher729 Sep 8 '20 at 21:26

$$O(n)$$ for the first section and $$O(n^2)$$ for the second, so $$O(n^2)$$ overall.