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?

  • 1
    $\begingroup$ How large can abs(a[i] - 1) be? $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.