The Gateway to Computer Science Excellence
0 votes

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?

in Algorithms by Junior (675 points)
edited by | 141 views
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.

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,291 answers
104,889 users