Purchase Solution

Solving a recurrence

Not what you're looking for?

Ask Custom Question

Solve the following recurrence exactly for n of the form 2^2^k.

T(2) = 1
T(n) = 2T(n^(1/2)) + log n

Express your answer as simply as possible using theta notation.
note added ** theta notation is based on big O notation

Show all work!

Purchase this Solution
Solution Summary

This shows how to solve a recurrence using theta notation.

Solution Preview

Proof:

Let n=2^2^k, then we have
T(n)=T(2^2^k)=2T(n^(1/2))+log ...

Purchase this Solution
Free BrainMass Quizzes
Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

Probability Quiz

Some questions on probability

Exponential Expressions

In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.

Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.

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.

View More Free Quizzes
Related BrainMass Solutions

  • solving the recurrence relation

    The solution is comprised of detailed explanations of solving the recurrence relation.

  • Find formula for sequence

    detailed explanation to first finding a recurrence for a_n, then solving the recurrence.

  • Solving a Recurrence Relation

    20538 Solving a Recurrence Relation Solve the following recurrence relation: a(n) = a(n-1) + 3(n-1), a(0) = 1 I know this should not be a difficult problem, but my main problem is in solving the problem when the coefficient of the a(n-1) term

  • Algebra: Simultaneous Recurrence Relations

    The expert solves a system of two recurrence sequences.

  • Recurrence Relations/Difference Equations

    49806 Solving Recurrence Relations/Difference Equations Solve the following difference equations/recurrence relations: a) b) c) Kindly show work in detail so I can understand the steps! Thanks!

  • Solving recurrence relations.

    20093 Solving recurrence relations. Find and solve a recurrence relation for the number of ways to make a pile of n chips using red, white, and blue chips and such that no two red chips are together.

  • Exponential generating function for number ordered partition

    Using a recurrence and solving a differential equation obtain the final solution: OS_3(x) = -1 + 3e^(x) - 3e^(2x) + e^(3x) b) Since OS(0,3) = 0, then OS (n,3) = 3-3*2^(n)+3^(n) for n greater than/equal to 1, and since S(0,3) = 0, then S(n,3) = 1/6[

  • Solutions of Recurrence Relations

    of a recurrence relation are found.

  • Fibonacci recurrence

    plugging in a and b values) Recurrence relationship at n = 2, G(3) = G(2) + G(1) is obviously true.

View More Related Solutions