Recurrences
Not what you're looking for?
Solve the recurrence T(n) = 2T(sqrt(n)) + 1 by making change of variables. The solution should be asymptotically tight.
2. Use a recursive tree to give an asymptotically tight solution to the recurrence T(n) = T(n-a) + T(a) + cn, where n > = 1 and c > 0 are constants.
Purchase this Solution
Solution Summary
This is two problems regarding recurrences.
Solution Preview
Question 1
----------
T(n) = 2T(sqrt(n)) + 1 ----- (1)
If you let n = m^2, then this is
T(m^2) = 2 T(m) + 1 ----- (2)
This is reminiscent of the law of logarithms
log (m^2) = 2 log m ----- (3)
to some base b.
However, there is a bugging "+ 1" constant term to deal with.
Let T(m) = log m + k ----- (4)
where k is a constant to be found.
Substituting into (2), we get
log m^2 + k = 2 (log m + k) + 1
2 log m + k = 2 log m + 2k + 1
canceling and solving, we get
k = -1
Therefore we guess T(m) to be of the form
T(m) = log m - 1
Since m is just a dummy variable, we can also write
T(n) = log n - 1
To verify asymptotic tightness:-
Suppose T(m) > T(b^2) [log m - 1] for all m >_ b
Multiply both sides by 2 and add 1, we get
2 T(m) + 1 > T(b^2) [2 (log m - 1) + 1]
T(m^2) > T(b^2) [2 log m - 1]
In particular,
T(b^2) > T(b^2) [2 log b - 1]
1 > 2 log b - 1
1 > log b
This cannot hold for all b. Therefore
there must exist some b and c2 such that
for all m >_ b
T(m) _< c2 (log m - 1) (c2 = T(b^2))
[The above inequalities can be tweaked to give a c1 so that
c1 (log m - 1) _< T(m).]
[The ...
Purchase this Solution
Free BrainMass Quizzes
Know Your Linear Equations
Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.
Solving quadratic inequalities
This quiz test you on how well you are familiar with solving quadratic inequalities.
Geometry - Real Life Application Problems
Understanding of how geometry applies to in real-world contexts
Exponential Expressions
In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.
Probability Quiz
Some questions on probability