Find running time of algorithm
Analysis, Asymptotic notation, Notions of space and time complexity, Worst and average case analysis; Design: Greedy approach, Dynamic programming, Divideandconquer; Tree and graph traversals, Connected components, Spanning trees, Shortest paths; Hashing, Sorting, Searching.
by dhingrak » Sun Sep 28, 2014 4:26 pm
T(n)= T(n1)+T(n2)+T(n3), 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
by Unnikuttan » Thu Dec 04, 2014 12:34 pm
dhingrak wrote:T(n)= T(n1)+T(n2)+T(n3), 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^3E^2E1 =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

 Posts: 498
 Joined: Fri Jun 28, 2013 4:34 pm
 My College/Company:: CUSAT
 Roll Number: 9999999
by Unnikuttan » Wed Dec 10, 2014 3:37 pm
has anyone find the answer..?
Unni.

Unnikuttan
 Gatementor Senior Member

 Posts: 498
 Joined: Fri Jun 28, 2013 4:34 pm
 My College/Company:: CUSAT
 Roll Number: 9999999
by 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^3E^2E1 =0....?

dhingrak

 Posts: 4
 Joined: Tue Sep 23, 2014 2:08 pm
 My College/Company:: Manav Rachna College
 Roll Number: 19520066
Return to Algorithms