I believe this question should be extremely easy but I am having a (embarrassing) hard time figuring out why its true if there exist OWF (computable in polynomial time) then there exits a OWF that is computed in $O(n^2)$.
This is what I have/tried.
Let $ \ f(x)$ be a OWF that can be computed in $k^c$. Then we can construct a OWF:
$$ f'(x'||\ x'') = f(x') || \ x'' $$ where: $$ |x'| = k \\ |x''| = k^c $$
Notice the size of the input for $f'$ is $n = k^c + k$.
Its intuitively "obvious" f' is a OWF since f is OWF (or you can go ahead and prove it by contradiction if you want to be pedantic). But how come it takes $O(n^2)$ to compute the OWF f'? Does this depend on the Turing Machine model being used to compute f'?
It seems to me you can just parse the input $x'||x''$ (separate it so that you can feed the appropriate thing to the original f) in O(n) and then compute $f(x')$ in $k^c = O(n)$ and then concatenate it to $x''$ and print f(x')|x'' (printing takes at most $O(n)$). It seems to me it takes $O(n)$ and that the bound $O(n^2)$ is unnecessarily un-tight (I know $cn + d = O(n) = O(n^2)$). Or maybe the parsing algorithm is "harder" than I expect it... even if you just append the lengths at the beginning just for parsing purposes , isn't the time to compute $f'$ just $O(n)$?
Does someone understands why my O(n) argument is wrong?