0

I have constructed an algorithm that runs in poly(log(G), log(x)). I am now asked to construct one that runs in poly(log(N), log(x)), where N>G. What would make the first algorithm not also run in poly(log(N), log(x))? (is the fact that N>G not enough?).

Thanks.

Anon
  • 1,757
  • Is poly(log(G), log(x)) an upper bound ($O(-)$)? Or must the exact runtime be precisely a polynomial in log(G) and log(x)? – A.M. Apr 13 '22 at 21:10
  • I think it's the latter, but what would be the case either way? – Anon Apr 13 '22 at 21:13
  • Someone told me it's the fact that $x$ can be "very large" that renders the first one not necessarily poly(log(N), log(x)), but I don't know what they meant by that exactly. – Anon Apr 13 '22 at 21:15
  • 1
    In the first case, $N>G$ so $\log N>\log G$ and a poly(log(G), log(x)) algorithm is a poly(log(N), log(x)) algorithm. In the latter case (which I actually think is unlikely), you need to know more about $N,G$ and what the algorithms are - but e.g. $\log G+2(\log G)^2\log x$ is literally a polynomial in $\log G$ and $\log x$ but not in $\log N$ and $\log x$. More details about the question are needed. (It can't be to do with the value of $x$ from the information you've given.) – A.M. Apr 13 '22 at 21:16

0 Answers0