Geek asks and answers

Recurrence T (n) = T (n ^ (1/2)) + 1

I looked at this repetition and wanted to check if I made the right decision.

T(n) = T(n^(1/2)) + 1
= T(n^(1/4)) + 1 + 1
= T(n^(1/8)) + 1 + 1 + 1
...
= 1 + 1 + 1 + ... + 1 (a total of rad n times)
= n^(1/2)

So the answer will come to a theta estimate of n ^ (1/2)

+4
source share
2 answers

hint: suppose n = 2 2 m or m = log2 log 2n, and you know that 2 2 m-1 * 2 2 m-1 = 2 2 m, so if you define S (m) = T (n), then your S will be:

S (m) = S (m-1) +1 → S (m) = Θ (m) → S (m) = T (n) = Θ (log 2 log 2 n)

extend it for the general case.

, T (n) = T (n/2) + 1, . Θ (logn). , , ( ), Θ (log log n).

+7

- , .

: enter image description here.

- , . 0, 1, 2, , 2 , : enter image description here.

, enter image description here.

, log(log(n)) , .

PS .

+10

More articles:


All Articles