T(n,k) = T(n^1/2) +k
כאשר k *אינו* קבועאני מניח שזה די דבילי, אבל לא בטוח כיצד לגשת לזה?
האם להשתמש בשיטת הניחוש ולומר שזה O(n^1/2+k) ?
אם אני הולך לפי זה יוצא לי שהקבוע שלי צריך להיות לפחות 1
אבל אני לא בטוח אם ככה עושים במקרה כזה
או שבכלל צריך ללכת על הצבה?
m = logn
n = 2^m
T(n,k) = T(2^m,k) = T(2^m/2)+k
לסמן:
S(y,k) = T(2^y,k)
S(m,k) = T(2^m,k) = S(m/2)+k
ואז ידוע ש:
S(m,k) = Teta(k*logm)
ואז מתקבל:
T(n,k) = T(2^m,k) = S(m,k) = Teta(k*log(logn))
???
באמת שאני לא מבין מה עושים פה למרות שזה בטח פשוט
אשמח לעזרה