# Determine smallest possible parameter set for FPT

I am reading a book about complexity analysis and cannot find a way to solve a problem in that book. The problem is, that I do not understand how to determine the smallest possible parameters, given the runtime of an algorithm. Do I just need to insert some numbers and see if the parameters exceed n at some point? Perhaps someone can explain that to me.

Consider the following exercise:

The following O(.) expressions represent worst-case runtimes of different algorithms, where n is a measure of the input size and p, q and r are parameters (where p, q, r <= n). Which of the following running times are FPT running times? Give the smallest possible parameter set for which the running times are FPT (if one exists) and explain.

a) $$O(p^q * n^2)$$

Now I know that by the definition of FPT, this runtime is FPT (because we have a function of the parameters times n^constant). However, what are the smallest $$p$$ and $$q$$ in that case?

There are some more, but I just want to understand how to solve it and then I'll try the rest myself again.

Taken from:

Rooij, I. V., Blokpoel, M., Kwisthout, J., & Wareham, T. (2019). Fixed-Parameter Tractable Time. In Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis (p. 125). Cambridge, England: Cambridge University Press.

Recall that the runtime must be of the form $$f(k) \cdot n^c$$ for some constant $$c$$. So I believe that the exercise is asking, given that all three are at most $$n$$, which do you have to take as formal parameters in your analysis to achieve an FPT runtime.
So if only $$p$$ is a parameter, is that FPT? What if only $$q$$? Clearly, if both are fixed, you have FPT runtime.