Prev: Analysis of detecting loops in a singly linked list.
Next: "Why Scripting Is Evil" -- comments?
From: Ben Bacarisse on 3 May 2010 07:11
mohangupta13 <mohangupta13(a)gmail.com> writes:
<snip>
> 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 )???

It's often very hard indeed.

I was about to say that in this case one can argue that if s and t are
the string lengths then O(s+t) run time is as good as one can get simply
because every element of both strings can contribute to the result but
that is not always true[1]. Determining if the space used by an
algorithm is optimal is often even harder.

Complexity theorists work with a very formal framework. Counting the
number of occurrences of each character in a string only uses O(1) space
in a framework where the counts can grow arbitrarily large without any
cost in terms of space. In most frameworks, this does not happen so the
space might have to grow logarithmically with the length of the input.

> I know its not always possible to say such things "for some
> problems"..but for major class of problems its know what is the best
> possible like for a comparison sort the lower bound is well know (nlg
> n).
>
> Any reference to some resource will also do ... ( some one previously
> referred me to " MIT lectures on Structure and Interpretation of
> computer programs" ..i did that but still the doubt persists.)

Knuth (The Art of Computer Programming) has a lot to say about this but
it is a huge and difficult work. All the texts I know of are old (since
I studied this sort of thing a while ago) but I certainly enjoyed "The
Design and Analysis of Computer Programs" by Aho, Hopcroft and Ullman.
I notice it is still in print. Do you have access to a good library?

There is probably some good material on the web, but finding it is hard.

<snip>

[1] Consider the family of pairs of strings (S1, S1+S2). The solution
is S1 and the length of the second string has no impact on the result.
--
Ben.
From: Pascal J. Bourguignon on 3 May 2010 11:45
mohangupta13 <mohangupta13(a)gmail.com> writes:

> This might be the fourth time I am asking it here (havn't got
> satisfactory answers yet).
>
> 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 )???

The answer depends on the specific given problem. (And a small change
to the specification of the problem may imply a big change in the
answer, and even switch the answer between provable, unprovable, and
unknow whether it's even provable or unprovable).


Intuitively the reason why it is so is similar to the reason why there
is no algorithm to determine of a potential algorithm terminates or
not. (If you had a way to explain how one can prove that a
complexicity of an algorith is the best we can do, applying it to
itself would (I'd guess) give inconsistent results).



> I know its not always possible to say such things "for some
> problems"..but for major class of problems its know what is the best
> possible like for a comparison sort the lower bound is well know (nlg
> n).

But as you say, if you have a specific problem we can then try to find
a specific proof.

For example, if the given algorithm must process every element of the
input, then it cannot do better than O(n). (Unless we consider quantum
algorithm where we can process the whole input (or chunks thereof) at
once).


> Any reference to some resource will also do...

To begin with, any text on algorithmics and complexity would cover
enough material to start to understand the question, and be able to
answer it in simple cases.
Google, or Google Book for algorithmic complexity ;-)

--
__Pascal Bourguignon__
http://www.informatimago.com
From: Patricia Shanahan on 4 May 2010 18:08
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
First  |  Prev  | 
Pages: 1 2 3
Prev: Analysis of detecting loops in a singly linked list.
Next: "Why Scripting Is Evil" -- comments?