I've been given the recursive function: T(n)=n^(2/3) T(n^(1/3))+C; T(n<=2)=O(1) With n=2^(3p) where p is a positive integer.

Dulce Cantrell

Dulce Cantrell

Answered question

2022-09-07

I've been given the recursive function:
T ( n ) = n 2 3   T ( n 1 3 ) + C
T ( n <= 2 ) = O ( 1 )
With n = 2 3 p where p is a positive integer.

Answer & Explanation

Baluttor7

Baluttor7

Beginner2022-09-08Added 17 answers

Step 1
If you get rid of cubic roots you get
T ( n 3 ) = n 2 T ( n ) + C
Notice that when you divide by n 3 you get something more homogeneous T ( n 3 ) n 3 = T ( n ) n + C n 3
So let set U ( n ) = T ( n ) n and we have
U ( n 3 ) = U ( n ) + C n 3
Now let set n = 2 p and T ( n ) = V ( p ) and we have
V ( 3 p ) = V ( p ) + C 8 p
Now let set p = 3 k and V ( p ) = W ( k ) and we have
W ( k + 1 ) = W ( k ) + C 8 3 k
This last one is telescopic therefore
W ( k ) = W ( 0 ) + i = 0 k 1 C 8 3 i
The problem is that this sum, does not really have a closed form, but the exponential grows very quickly so the sum also converges very quickly and we can estimate that W is basically constant, i.e.
W ( k ) = O ( 1 ) , so that T ( n ) = O ( n )

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?