Si des fonctions unidirectionnelles (OWF) existent, alors il sort un OWF qui est calculable en temps quadratique par un argument de rembourrage

Question

Je crois que cette question devrait être extrêmement facile, mais j'ai un mal de mal (embarrassant) pour comprendre pourquoi il est vrai s'il existe un OWF (calculable en temps polynomial), puis il sort d'un OWF qui est calculé dans $ o (n ^ 2) $ .

C'est ce que j'ai / essayé.

Soit $ f (x) $ un OWF qui peut être calculé dans $ k ^ c $. Ensuite, nous pouvons construire un OWF:

$$ f '(x' || x '') = f (x ') || x '' $$ où: $$ | x '| = k | x '' | = k ^ c $$

Remarquez la taille de l'entrée pour $ f '$ est $ n = k ^ c + k $.

Son intuitivement "évident" f 'est un OWF car F est OWF (ou vous pouvez aller de l'avant et le prouver par contradiction si vous voulez être pédante). Mais comment se fait-il qu'il faut $ o (n ^ 2) $ pour calculer l'Owf f '? Cela dépend-il du modèle de machine Turing utilisé pour calculer f '?

Il me semble que vous pouvez simplement analyser l'entrée $ x '|| x' '$ (séparez-la afin que vous puissiez nourrir la chose appropriée au F) en o (n), puis calculer $ f (x') $ Dans $ k ^ c = o (n) $ puis le concaténer à $ x '' $ et imprimer f (x ') | x' '(l'impression prend au plus $ o (n) $). Il me semble qu'il faut $ o (n) $ et que la limite $ o (n ^ 2) $ est inutilement inutile (je sais $ cn + d = o (n) = o (n ^ 2) $) . Ou peut-être que l'algorithme d'analyse est "plus difficile" que ce à quoi je m'attends ... même si vous ajoutez simplement les longueurs au début juste à des fins d'analyse, n'est-ce pas le moment de calculer $ f '$ juste o (n) $?

Est-ce que quelqu'un comprend pourquoi mon argument O (n) est faux?