מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/מציאת סיבוכיות פסוודו-קוד/תרגילים/קריאות רקרורסיביות בלולאת קפיצות שורש/שאלה

הפונקציה Alg מוגדרת כך:

Alg(A, i, j)
1	if j <= i + 1
2		return
	
3	q = Sqrt(j - i + 1) # q = ⌊(j - i + 1)^(1/2)⌋
4	for k in [0, ..., q - 1]
5		Alg(A, i + k * q, i + (k + 1) * (q - 1))

6	Proc(A, i, j)

היא משתמשת בשתי הפונקציות הבאות:

1. הפונקציה Sqrt(n) מחזירה את השורש הריבועי של $\displaystyle n$ מעוגל כלפי מטה. היא פועלת בזמן $\displaystyle O(1)$.
2. הפונקציה Proc היא פונקציה כלשהי המקיימת שזמן ריצת Proc(A, i, j) הוא $\displaystyle \Theta (j-i)$.

מהו זמן הריצה של Alg(A, 1, n)?