Skip to main content
Computer Science

Return to Question

3
duplicates list edited from Solving or approximating recurrence relations for sequences of numbers to Solving or approximating recurrence relations for sequences of numbers, Can you always prove the asymptotic bound of a recurrence of the form aT(n/b) + f(n) using the substitution method?
Link
D.W. ♦
D.W. ♦
  • 165.6k
  • 21
  • 230
  • 490
Post Closed as "Duplicate" by David Richerby, D.W.♦
added 49 characters in body; edited title
Source Link
Yuval Filmus
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

Substitution method for T$T(n) = 2*2T(7n/10) + O (1)$

Substitution method for T(n) = 2*(7n/10) + OI want to solve (1)$T(n) = 2T(7n/10) + O (1)$ using the substitution method.

I am thinking it is nlog(n)think the solution should be $T(n) = O(n\log n)$, but iI am having trouble constructing a proof by substitution.

Substitution method for T(n) = 2*(7n/10) + O (1)

Substitution method for T(n) = 2*(7n/10) + O (1)

I am thinking it is nlog(n) but i am having trouble constructing a proof by substitution.

Substitution method for $T(n) = 2T(7n/10) + O (1)$

I want to solve $T(n) = 2T(7n/10) + O (1)$ using the substitution method.

I think the solution should be $T(n) = O(n\log n)$, but I am having trouble constructing a proof by substitution.

Source Link
Arnold
Arnold
  • 1

Substitution method for T(n) = 2*(7n/10) + O (1)

Substitution method for T(n) = 2*(7n/10) + O (1)

I am thinking it is nlog(n) but i am having trouble constructing a proof by substitution.