Recurrence relation of a recursive function

nicholaskong100 said:
Is there any critique about each step?
Click to expand...
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?
 
Dr.Peterson said:
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?
Click to expand...
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
 
You haven't actually quoted the problem statement yet, as requested.
nicholaskong100 said:
Step 2: Expand the recursive function three times
Click to expand...
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.
nicholaskong100 said:
Step 3: Write the last T(n) in terms of i
Click to expand...
How is i defined?
nicholaskong100 said:
Find c and n when claiming the equation is Big O
Click to expand...
What does this refer to? Will we understand when you state the problem fully?
 
You must log in or register to reply here.
Top