patternMinor
Exponential time algorithms
Viewed 0 times
exponentialtimealgorithms
Problem
Wiki define Polynomial time as fallow:
An algorithm is said to be of polynomial time if its running time is
upper bounded by a polynomial expression in the size of the input for
the algorithm, i.e., $T(n) = O(n^k)$ for some constant $k$
I understand that in general speaking the difference between Polynomial time and Exponential time is that exponential function grows strictly faster than any polynomial function, asymptotically(reference).
I am trying to understand the core definition of Exponential time.
An algorithm is said to be of polynomial time if its running time is
upper bounded by a polynomial expression in the size of the input for
the algorithm, i.e., $T(n) = O(n^k)$ for some constant $k$
I understand that in general speaking the difference between Polynomial time and Exponential time is that exponential function grows strictly faster than any polynomial function, asymptotically(reference).
I am trying to understand the core definition of Exponential time.
- What elements will make one algorithm to run in Exponential time?
- What change do I need to do in the polynomial expression to make it Exponential time?(By it I am referring to the algorithm definition in the beginning of the question)
Solution
-
There's no easy answer for this one, though there are signs to look out for. Examining every possible subset of a set, for instance, is exponential - so if I had a set of integers $\{x_1,...,x_n\}$, and wanted to check every subset of these to see if they sum to $0$, I'd have to consider exactly $2^n$ subsets, which makes this method exponential time. Several different traps can make an algorithm exponential time, however, so rather than looking out for broad categories, analyse algorithms on a case-by-case basis.
-
If an algorithm takes $n^2$ steps to complete, then it's polynomial. If it takes $2^n$ steps, it's exponential. The difference is the position of the $n$. If something is $O(n^m)$ for $n> 1$, $m>0$, then it's polynomial in $n$ for fixed $m$, but exponential in $m$ for fixed $n$.
There's no easy answer for this one, though there are signs to look out for. Examining every possible subset of a set, for instance, is exponential - so if I had a set of integers $\{x_1,...,x_n\}$, and wanted to check every subset of these to see if they sum to $0$, I'd have to consider exactly $2^n$ subsets, which makes this method exponential time. Several different traps can make an algorithm exponential time, however, so rather than looking out for broad categories, analyse algorithms on a case-by-case basis.
-
If an algorithm takes $n^2$ steps to complete, then it's polynomial. If it takes $2^n$ steps, it's exponential. The difference is the position of the $n$. If something is $O(n^m)$ for $n> 1$, $m>0$, then it's polynomial in $n$ for fixed $m$, but exponential in $m$ for fixed $n$.
Context
StackExchange Computer Science Q#18744, answer score: 7
Revisions (0)
No revisions yet.