What is the + n for

For this algorithm,

Bugs(n)
    if开发者_运维技巧 n = 0 generate 5 bugs
    else 
        Bugs(n-2);
        for i ← 1 to n
            generate 1 bug
        Bugs(n-2);

The Recurrence relation is: T(n) = 2T(n-2) + n, T(0) = 5

Why is there a +n? Is it because their is only one for loop, so if their would be two for loops would it be + n^2?

---

Well look at what it does for the n != 0 case:

• It calls Bugs(n-2) - so T(n-2) for this part
• It generates n bugs - so n assuming "generate 1 bug" is constant
• It calls Bugs(n-2) - so T(n-2) again

Total: 2T(n-2) + n