Find running time of algorithm

Analysis, Asymptotic notation, Notions of space and time complexity, Worst and average case analysis; Design: Greedy approach, Dynamic programming, Divide-and-conquer; Tree and graph traversals, Connected components, Spanning trees, Shortest paths; Hashing, Sorting, Searching.

Find running time of algorithm

Postby dhingrak » Sun Sep 28, 2014 4:26 pm

T(n)= T(n-1)+T(n-2)+T(n-3), n>3
= n ,otherwise
The order is
a) n b) log n c) n^n d) n^2

Can anyone please reply how to approach this problem..?Ans is given (a)
dhingrak
 
Posts: 4
Joined: Tue Sep 23, 2014 2:08 pm
My College/Company:: Manav Rachna College
Roll Number: 19520066

Re: Find running time of algorithm

Postby Unnikuttan » Thu Dec 04, 2014 12:34 pm

dhingrak wrote:T(n)= T(n-1)+T(n-2)+T(n-3), n>3
= n ,otherwise
The order is
a) n b) log n c) n^n d) n^2

Can anyone please reply how to approach this problem..?Ans is given (a)



the eq can be written as E^3-E^2-E-1 =0 it is a higher order(here it is 3) linear recurrence reln.

but this eq will not have any real roots...

are you sure that this is the correct equation..?

Unni.
Unnikuttan
Gatementor Senior Member
Gatementor Senior Member
 
Posts: 498
Joined: Fri Jun 28, 2013 4:34 pm
My College/Company:: CUSAT
Roll Number: 9999999

Re: Find running time of algorithm

Postby Unnikuttan » Wed Dec 10, 2014 3:37 pm

has anyone find the answer..?


Unni.
Unnikuttan
Gatementor Senior Member
Gatementor Senior Member
 
Posts: 498
Joined: Fri Jun 28, 2013 4:34 pm
My College/Company:: CUSAT
Roll Number: 9999999

Re: Find running time of algorithm

Postby dhingrak » Sat Dec 20, 2014 12:38 am

Unnikuttan wrote:has anyone find the answer..?


Unni.


can you please explain how did you converted the given question to

E^3-E^2-E-1 =0....?
dhingrak
 
Posts: 4
Joined: Tue Sep 23, 2014 2:08 pm
My College/Company:: Manav Rachna College
Roll Number: 19520066


Return to Algorithms

Who is online

Users browsing this forum: No registered users and 10 guests
cron