MadeEasy Test Series 2019: Algorithms - Time complexity

243 views

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?

edited
0
can't see "foo"
0
Sorry, was asking for bar(), edited
0
you can write it as,

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

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

0
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?
1
Yes.What matters is how many times the function is getting called. It is getting called twice in your example.
0
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.

Related questions

1
160 views
Please show the ideal way to deal with such comparisons as I am getting g>=f IN genral what logic shall be followed to analyse such complex comparions?
O($n^2$) O(n) O(nlogn) O($n(logn)^2$