Re: Finding the common elements in two strings .
- From: Patricia Shanahan <pats@xxxxxxx>
- Date: Wed, 05 May 2010 06:08:47 +0800
How can one prove (either mathematically or just by intuition ) that....
the run time of an algorithm or the memory use of it is the best we
can do for the particular problem ??? ( I mean how can one say that a
particular algorithm is the best for the given problem )???
There is no known general way to do that. There are a few cases in which
there is a provable lower bound and a known algorithm that achieves that
Depending on what the method measured, a best-algorithm test might solve
the P=NP question, earning a million dollar prize. We would apply it to
a known exponential time algorithm for an NP-complete problem. If that
is the best we can do, P is a proper subset of NP. If not, P and NP
might be equal.
As it is, in most cases, we can only talk about the fastest *known*
algorithm, leaving open the possibility of future improvement.
- Prev by Date: Re: Overhead of Disk Read and write , Input/ output , etc
- Next by Date: Converting from 0 and 1 to -1 and 1
- Previous by thread: Re: Finding the common elements in two strings .
- Next by thread: Cheap Software Offers!