# Math Help - Algorithms

1. ## Algorithms

Show that an algorithm that makes at most a constant number of calls to polynomial time subroutines runs in polynomial time, but that a polynomial number of calls to polynomial-time subroutines may result in an exponential time algorithm.

For the first part, can I say that the algorithm runs in O(x^m) where x^m is the longest run time of all the subroutines?

I have no idea for part 2

2. For the first question you answer is correct. About this second you have to notice that if your program performs $a_kx^k + ... + a_0$ operations, its lower and upper bound is $cx^{k+1}$ (think why?). So if number of executed subroutines is constant, maximal k will always be constant (assuming it depends on number of executions, but I think that's what the task is about, becuse if complexity of execution of one subroutine is indepentant, then it will be only product of two polnynominals, so polnynominal), but otherwise (polynominal number of executions) it can rise to the number of exections, which is polynominal, so we will get complexity like $\Theta(n^{p(n)})$, where $p(n)$ is a polynominal.