The Gateway to Computer Science Excellence
0 votes
141 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?

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

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
198,209 comments
104,889 users