سوال ۸۴ کنکور ارشد علوم کامپیوتر ۱۴۰۱

فرض کنید $f:\mathbb{N}\to\mathbb{N}$ یک تابع باشد که برای هر $i$، محاسبه $f(i)$ در زمان $\Theta(\sqrt{i})$ ممکن باشد. همچنین برای هر $i$ و $j$ که $1\le i\le j\le n$ تعریف می‌کنیم:

$g(i,j)=\begin{cases} f(i) & \text{اگر } i=j \\ \max_{i<k\le j}\{\,g(i,k-1)+g(k,j)\,\} & \text{اگر } i<j \end{cases}$

محاسبه $g(1,n)$ با الگوریتم پویا (دینامیکی) ساده‌ای که از رابطه بالا حاصل می‌شود، از چه مرتبه زمانی است؟