[Cs4800] Quick question about polynomial time

[Kenneth K Sham]

Andrei,
You are right. n^2 is polynomial and not exponential. Exponential would be
something like 2^n. Exponential time algorithms grow much faster than
polynomial. For example:

500^3  is far less than  3^500.  I'm pretty sure it's even far less than
2^500.

Ken


On Mon, Oct 11, 2010 at 5:47 PM, Andrei Mackenzie <andrei at ccs.neu.edu>wrote:

> Hi all,
>
> Assuming we let m = |M| and n = # of directed trees whose GCP we are
> interested in, would an algorithm that is bounded by O(n^2 * m) be
> considered polynomial? I don't think it's exponential, since neither n nor m
> appear as an exponent, but I'm not sure if it's still polynomial.
>
> Thanks in advance!
>
> --
> Andrei Mackenzie
>
> _______________________________________________
> Cs4800 mailing list
> Cs4800 at lists.ccs.neu.edu
> https://lists.ccs.neu.edu/bin/listinfo/cs4800
>
-------------- next part --------------
HTML attachment scrubbed and removed