Recurrence relation of a recursive function

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
12,598
Is there any critique about each step?
I think you are trying to find an explicit formula for T by looking for a pattern.

One comment is that I think you need to expand expressions like
1632095153232.png
in order to see the correct pattern.

Another is that these are not equivalent:
1632095265207.png
That probably won't be used in the correct solution, but you do need to learn to be careful with logs.

A thought about the problem itself: Have you considered what happens if n is not a power of 2? I started by calculating T(2), T(3), T(4), and this is instructive. Your final answer is likely to involve something like the greatest-integer function.

One specific question: Can you tell us what steps you were taught to take, so we can understand your approach?
 

nicholaskong100

New member
Joined
Aug 1, 2021
Messages
29
I think you are trying to find an explicit formula for T by looking for a pattern.

One comment is that I think you need to expand expressions like
View attachment 28958
in order to see the correct pattern.

Another is that these are not equivalent:
View attachment 28959
That probably won't be used in the correct solution, but you do need to learn to be careful with logs.

A thought about the problem itself: Have you considered what happens if n is not a power of 2? I started by calculating T(2), T(3), T(4), and this is instructive. Your final answer is likely to involve something like the greatest-integer function.

One specific question: Can you tell us what steps you were taught to take, so we can understand your approach?
Step 1: Write the recursive function
Step 2: Expand the recursive function three times
Step 3: Write the last T(n) in terms of i
Step 4: Take the input of T(n) from step 3 and set it to the value of the base case. And solve for i.
Step 5: Plug the value of i in the equation from step 3.

Find c and n when claiming the equation is Big O
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
12,598
You haven't actually quoted the problem statement yet, as requested.
Step 2: Expand the recursive function three times
You haven't expanded, as I use the term. In particular, your step 3 has an expanded form, which doesn't match your results from step 2.
Step 3: Write the last T(n) in terms of i
How is i defined?
Find c and n when claiming the equation is Big O
What does this refer to? Will we understand when you state the problem fully?
 
Top