Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Exponential time algorithm

  1. Aug 10, 2006 #1
    can sombody pls explain to me what does exponential time algorithm means??

  2. jcsd
  3. Aug 10, 2006 #2


    User Avatar
    Science Advisor

    Last edited by a moderator: May 2, 2017
  4. Aug 10, 2006 #3
    it is just some very basic computer question which is algorithm.It is not a programming problem.
    It means an algorithm which take exponential time to complete and another type is it takes polynomial time to compete an algorithm.

    Therefore,i do not understand what it means by exponential time and polynomial time
  5. Aug 10, 2006 #4


    User Avatar
    Science Advisor

    If an algorithm takes exponential time, that usually means that it can be done in
    [tex]\Theta (a^n)[/tex] time for some constant a.
    If an algorithm takes polynomial time, that usually means it can be done in
    [tex]\Theta (P(n))[/tex] time for some polynomial P.
    Are you familiar with [tex]\Theta[/tex], O, or [tex]\Omega[/tex] notation?
  6. Aug 10, 2006 #5
    Just to show a quick example of polynomial time. Say you have two nested for loops,
    for (i=1; i<n; i++) {
    for (j=1; j<n; j++) {}

    we can see that j goes to n as i = 1, then j goes to n as i = 2...you see a pattern? j goes to n, n times. Thus our running running time is
    n * n ...which also happens to be n^2...this is what is meant by polynomial time..a run time that can be expressed in polynomial form..[tex]a_nx^n + a_{n-1}x^{n-1} + \cdots + a_0[/tex]
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook