# Runtime analysis with recursion factor

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!

• You're not executing foo eight times but rather just multiplying the result of foo by eight. May 16 '16 at 18:11
• – Raphael
May 16 '16 at 18:44
• Neither recurrence is accurate.
– Raphael
May 16 '16 at 18:44
• cs.stackexchange.com/questions/57438/…
– D.W.
May 17 '16 at 3:33
• Also posted on SO. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted.
– D.W.
May 17 '16 at 3:34

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$.