Let $A=\lbrace (x,y)\in{\mathbb N}^2 | 0<x<y \rbrace$. For positive integers $u,v$ let $\rho(u,v)=(\textsf{min}(u,v),\textsf{max}(u,v))\in A$. It is easy to see that there is a unique map $f:A\to {\mathbb N}$ satisfying $f(x,x)=x$ for every $x$ and
$$ f(x,y)=\left\lbrace\begin{array}{lcl} 2f(\frac{x}{2},\frac{y}{2}) & \text{if } & x,y \text{ are both even}, \\ 2f(\frac{x}{2},y) & \text{if } & x \text{ is even}, y\text{ is odd}, \\ 2f(\rho(x,\frac{y}{2})) & \text{if } & x \text{ is odd}, y\text{ is even}, \\ 2f(\rho(x,\frac{y-x}{2})) & \text{if } & x,y \text{ are both odd} \\ \end{array}\right. $$
Next, let $g(n)=\textsf{max}_{1\leq x,y \leq n}f(x,y)$. I ask if there is a polynomial $h$ such that $g(n)\leq h(n)$. I have checked with a computer that $g(n)\leq n^2$ for $1\leq n \leq 1000$, but I don't know how to prove/disprove it in general.