I have this code:

if n is even
for i=1....n
   for j=1...i
      print j
return 8*foo(n/2)

Asking to calculate the running time $T (n)$. I thought at first that I can write the function like this:

$$T(n)= 8T(n / 2)+n^2$$ But according to the answers of the quiz, they are saying that the function looks like this:

$$T (n)= T(n / 2)+n^2$$ Why we can delete 8? Thank you very much!


1 Answer 1


You're asked to calculate the running time of the segment, not the value returned. In terms of running time, multiplication by 8 is a single operation, so the running time is (roughly) $T(n)=T(n/2)+n^2$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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