MadeEasy Test Series 2019: Algorithms - Time complexity

Question

cant we write the recurrance relation for bar() as T(n) = 5T(n-1) + c,
like cant we take both the recurrance call as combined as both have same parameter?
and if not, then how to solve such?

Comments

can't see "foo"

---

Sorry, was asking for bar(), edited

---

you can write it as,

bar(n)= bar(n-1) + bar(n-1) = 2bar(n-1)

---

@Markzuck It is 3 multiplied by what bar(n-1) returns and not 3 bar(n-1) function calls. 

---

Ohh got it
So while calling we need to write separately?
Like 5*tn-1 means 5*return value

But in complexity eqn we just write number of times called which is 2?

Not 5tn-1 right?

---

Yes.What matters is how many times the function is getting called. It is getting called twice in your example.

---

I don't understand how it gets T(n) = O(2^n). I try solving it and I am getting this equation:

T(n) = 2^(n-1) * 3^(n) + ( 2^(n-2) -1 )

so by this leading term will be O(2^n * 3^n)

Please if someone know where I did this wrong.

Answer 1

2T(n-1)+1 will give us O(2^n)