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

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)