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 smalles 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.

An example is: $ 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?

Thank’s in advance. Cheers!

EDIT:

The exercise is: The following O(.) expressions resprent 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 smalles possible parameter set for which the rinning times are fpt (if one exists) and explain.

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

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.