#### nicholaskong100

##### New member

- Joined
- Aug 1, 2021

- Messages
- 30

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter nicholaskong100
- Start date

- Joined
- Aug 1, 2021

- Messages
- 30

- Joined
- Jun 18, 2007

- Messages
- 26,708

We do not know the problem statement of your assignment!

Please post the exact problem as it was given to you.

- Joined
- Nov 12, 2017

- Messages
- 13,641

I think you are trying to find an explicit formula for T by looking for a pattern.Is there any critique about each step?

One comment is that I think you need to expand expressions like

in order to see the correct pattern.

Another is that these are not equivalent:

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?

- Joined
- Aug 1, 2021

- Messages
- 30

Step 1: Write the recursive functionI 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 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

- Joined
- Aug 1, 2021

- Messages
- 30

Before I list the 5 steps, the first is a base case and the second is a recursive case of a function,

Please post the exact problem as it was given to you.

- Joined
- Nov 12, 2017

- Messages
- 13,641

You haven'tStep 2: Expand the recursive function three times

How is i defined?Step 3: Write the last T(n) in terms of i

What does this refer to? Will we understand when you state the problem fully?Findc and nwhen claimingthe equationis Big O