Re: Finding the common elements in two strings .

mohangupta13 wrote:
....
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
bound.

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.

Patricia
.

Relevant Pages

  • Re: Turing Machines and Physical Computation
    ... rather than adumbrated in that 1936 Turing paper On Computable ... ... any actual computer has finite memory, ... computer will run out of memory for some huge calculation. ... It is generally assumed that an algorithm must satisfy the following ...
    (comp.theory)
  • Re: Turing Machines and Physical Computation
    ... rather than adumbrated in that 1936 Turing paper On Computable ... ... any actual computer has finite memory, ... computer will run out of memory for some huge calculation. ... It is generally assumed that an algorithm must satisfy the following ...
    (sci.math)
  • [Meta] for the record - please ignore (was Re: how to transpose large matrix?)
    ... Isn't it a bit pointless to include that attribution line then? ... asked for a solution that would save memory, ... going to compare an Oalgorithm to an Oalgorithm. ... computational complexity of storing the entire matrix in memory. ...
    (comp.unix.shell)
  • Solving the memory issue of lock-free algorithms
    ... I read a lot about lock-free algorithm and tried to find an "elegant" ... solution to the memory problem that the algorithms poses. ... LFStackNode *Next; ... xor eax, eax ...
    (comp.programming.threads)
  • Re: Version after Version
    ... MMX, by doing 50 times two additions at a time. ... Many compilers & memory managers have at least the option to align data on ... > - compression and decompression works at the Bit level ... > LZW is the until recently proprietory algorithm of Uinisys ...
    (alt.comp.lang.borland-delphi)