I'm having a difficult time understanding time complexities of algorithm. I know that a polynomial time is of the form O(n^m) where m is a constant. Consider the following case where A is a list of elements:
Foo(A)
for each element a in A:
for each element b in A-a:
Polynomial-Time-Algorithm-Bar(A, a, b)
If n is the size of A,
1) Am I right in understanding that Foo(A)
is also a polynomial time algorithm , because the function Polynomial-Time-Algorithm-Bar
is called (n-1)*n
times ?
2) When would an algorithm making calls to another polynomial time algorithm become exponential. I understand that if it has a running time of O(n^m) and m is variable and n is constant, then it would be exponential. Can you give me an example of such a case in the above example?