4
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

When we talk about quadratic running time, we mean $O(n^2)$ running time where $n$ is the length of the input -- i.e., the running time is a constant times the square of the length of the input. Make sure you understand what the length of the input is here. By padding the input, we've made the input longer. Even though the overall running time doesn't change, the size of the input is larger, so relatively speaking, the running time is now a slower-growing function of the input size.

For instance, suppose $f$ can be computed in cubic time: in $O(k^3)$ time, where $n$ is the length of the input to $f$. Now consider the padded function $f'$, which has been padded out to the length $k^{1.5}$. What is the running time of $f'$? Its running time remains $O(k^3)$, but now the input is of size $k^{1.5}$. Re-expressing the running time of $f'$ as a function of its input size, we let $n=k^{1.5}$ be the length of the input to $f'$, and then notice that $k^3=n^2$, so the running time of $f'$ is $O(n^2)$: quadratic in the size of its input.


On your specific question: yes, the $O(n^2)$ seems unnecessarily loose. Your argument that the running time of $f'$ is $O(n)$ (linear in the length of its input) looks right to me. I don't know why they mentioned $O(n^2)$ as opposed to $O(n)$.

$\endgroup$
  • $\begingroup$ Your answer made me unsure whether I understand what is the length of the input to f'. I defined in my question what I thought the length of the input is to f' and tried justifying why it ran in linear time wrt to that input, was that not correct? Also, I did read and understand ur example and it makes sense. Unfortunately, I am still not sure why my original approach is still incorrect. $\endgroup$ – Charlie Parker Jan 7 '14 at 0:37
  • $\begingroup$ (by unsure, I guess I meant, it made me question). $\endgroup$ – Charlie Parker Jan 7 '14 at 1:16
  • 1
    $\begingroup$ @CharlieParker, ahh, OK, I see what you mean. I edited my answer. I agree with your reasoning. I don't think your reasoning is incorrect. $\endgroup$ – D.W. Jan 8 '14 at 6:44
  • $\begingroup$ Your example still proved extremely useful because it made it extremely clear for me what the point was (which I had a hard time appreciating because of the looseness of the bound that was bothering me). Thanks! :) $\endgroup$ – Charlie Parker Jan 8 '14 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.