Mergesort Recursion Tree: Big O

[coral grove]

I'm trying to solve this but i dont know how to do so when the equation doesnt have big O or omega to make a recursion tree with and im not sure if i need it or not

[pallid cairn]

1. Wait patiently for a helper to come along.
2. Once someone helps you, say thank you and close the thread with:

+close

3. Feel free to nominate the person for helper of the week in #helper-nominations
4. Do not ping the mods, unless someone is breaking the rules.
5. If you're happy with the help you got here, and the server overall, you can contribute financially as well:

[coral grove]

This is the example given

[hollow vale]

convincing argument

master theorem of time complexity

[coral grove]

wha t

i know what it is but i dont really get how to solve it

[cold glade]

Should be possible to solve this exactly.

[coral grove]

exactly how

[cold glade]

We have:
T(n) = 2T(n/2) + n^3
Let n = 2^k. Then:
T(2^k) = 2T(2^(k - 1)) + 2^(3k)
Let a(k) = T(2^k). Then:
a(k) = 2a(k - 1) + 2^(3k)
This is now a linear recurrence relation. Can you continue from here?

Any progress?

[coral grove]

im currently out right now but ill work on it as soon as i get back

[cold glade]

Oh, alright.

[coral grove]

but im not sure eif this is the method they want us to use but im also sort of clueless on how to do this

like i know i have to make a tree but not how to build it

[cold glade]

Well, yeah. I've heard of master theorem Al was talking about above, but I don't know it.

At least, when you solve the recurrence exactly, you'll know what to expect.

[coral grove]

where did you get 2T(n/2)?

[cold glade]

Well, you wrote it in your picture.

Oh, wait.

You didn't write it correctly, I think.

Well, no matter, the approach is the same.

T(n) = T(n/2) + n^3
Same as above...
a(k) = a(k - 1) + 2^(3k)

[coral grove]

thats not the question thats the example

[cold glade]

Oh, I see. Well, in any case, the approach is the same.