Let $f:N\rightarrow N$ and for all $i$ we have $f(i)\in \Theta(\sqrt i)$. For all $i, j$ such that $1\le i\le j\le n$ we define
$$g(i, j)=\begin{cases}f(i)& i=j\\\max_{i<k\le j}\{g(i,k-1)+g(k,j)\}& i<j\end{cases}$$
What's the time complexity of $g(1,n)$?