Recent content by Ad2d

Sorry for the confusion. You right when you stated that when n=2k that f(n/2) becomes f(2k/2) which goes to f(2k-1). For the f(n-1) I may have skipped a step when substitution. I meant to say: f(k) =2f(2k-1). + 2k -1 then after that I started my substitution. My qeustion was that when I did...

I think that k's are fixed value for a give problem, and that as n-> infinite that one of those will be >, <, or =. I think that is what gear2d is asking.

Homework Statement I have recurrence relation problem and what to ask would my way be just as correct as the TA did the solution: f(n) = 0, n=1 and 2f(n/2) + n -1 The Attempt at a Solution Here we assume n = 2k This is my way: f(k-1) = 2[2f(2k-2)*2k-1-1] + 2k - 1 =...

I made a big mistake. Here is what I have after rethinking it: f(n) = 2f(n/2) + n - 1 = 2[2f(n/4) + n/2 - 1) + n -1 = 4f(n/4) + 2n - 3 = 4[2f(n/8) + n/4 - 1) + 2n -3 = 8f(n/8) + 3n - 7 = 8[2f(n/16) + n/8 - 1) + 3n -7 = 16f(n/4) + 4n - 15 Guess: f(n) = 2kf(n/2k) + kn - (k-1) we know from...

Homework Statement f(n) = 0 when n=1 and 2f(n/2) + n - 1 when n is otherwise Homework Equations Repeated substitution The Attempt at a Solution f(n) = 2f(n/2) + n - 1 = 22f(n/22) + n - 3 = 23f(n/23) + n - 7 = 24f(n/24) + n - 15 Guess: f(n) = 2kf(n/2k) + n...

Thank You HallsofIvy for the help. I spoke to the teacher about this and apparently big K and little k are the same thing (K1=k1, K2 = k2), so would this change anything?

Homework Statement Compare each pairs according to their respective orders. Classify these forms by the relationships between the indicated constants. Note: ki is a constant and all kis are mutually independent. (ki < kj where i < j), ki ≥1.0. 1) n! Vs. K1^ n => Here its Cap K not...

Thank You all. I was able do what CRGreathouse with the limits which made more since to me. From what the professor was saying, I am thinking that Theta is a value that is I am between the upper and lower bound, and I need to show whether or not the functions where less than the upperbond (f(n)...

Hello All, I need help making sure I am right about this. Say for example I have these two functions: f(n) = 2^n and g(n) = 3^n. Now the order is O(2^n) and O(3^n) respectfuilly. Now I need make sure I am right about this: based on the order, O(2^n) < O(3^n) therefore f(n) < THETA(g(n))...