[Subject Prev][Subject Next][Thread Prev][Thread Next][Subject Index][Thread Index]

Re: "time complexity"

From: Shridhar Daithankar <shridhar_daithankar@xxxxxxxxxx>

I guess it depends upon the algorithm you are using too, unless you are
calculating time complexity of storage and retrieval itself.
Yes, storage and retrieval is the core issue.
I have implemented a solution to knapsack(0/1) problem using dynamic programming. To prevent unnessary recursive function calls. I've stored the calls and the corresponding results in a map(I think a "quasi-heap" implementation). Now I want to know if this is more efficient then a "tuple" method suggested in a text-book, which uses a list to do the same.

I have to do something with the travelling salesman problem. Due to the combination of recursion and associative storage, I'm unable to theoretically approximate the complexity. The flow of the program is not "simple/predictable".

Even if I know for the complexities of the storage and retrieval algos, (log n, I think) I cannot work out a correct solution. That's why I need a program to determin time-complexity.

Somebody spoke about using a graph to approximate the complexity. Is there a software available for this. Or even this has to be done manually.

I would like to know result of your experiment. My initial guess is that they
affect the time complexity in a simple predictable way depending upon the
(Looks silly, isn't it?)


Rajeev Rao wrote:

> If I use a specialised container, such as a map or priority que, provided by > the STL, I would like to their impact on the time-complexity. It would take > a lot of time to look at the STL implementations, hence a computer doing the
> job would be nice.

The mailing list archives are available at

Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com.