Skip to main content
Computer Science

Return to Question

deleted 8 characters in body
Source Link
Yuval Filmus
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

I am trying to solve the following recurrence $T(n) = 4T(n/2) + n^3$ with substitution method. My guess is $T(n) = \Theta (n^3)$ (I used master theorem) and I tried to show that $T(n) \leq cn^3$. But, when iI substitute iI got $T(n) \leq c \frac{n^3}{2} + n^3$ and that's it not the exact form of the guess, so it doesn't work. How can I solve this recurrence? Thanks.

I am trying to solve the following recurrence $T(n) = 4T(n/2) + n^3$ with substitution method. My guess is $T(n) = \Theta (n^3)$ (I used master theorem) and I tried to show that $T(n) \leq cn^3$. But, when i substitute i got $T(n) \leq c \frac{n^3}{2} + n^3$ and that's it not the exact form of the guess, so it doesn't work. How can I solve this recurrence? Thanks.

I am trying to solve the following recurrence $T(n) = 4T(n/2) + n^3$ with substitution method. My guess is $T(n) = \Theta (n^3)$ (I used master theorem) and I tried to show that $T(n) \leq cn^3$. But, when I substitute I got $T(n) \leq c \frac{n^3}{2} + n^3$ and that's it not the exact form of the guess, so it doesn't work. How can I solve this recurrence?

Source Link
Vincenzo Iannucci
Vincenzo Iannucci
  • 33
  • 2
  • 5

Solving $T(n) = 4T(n/2) + n^3$ with substituton method

I am trying to solve the following recurrence $T(n) = 4T(n/2) + n^3$ with substitution method. My guess is $T(n) = \Theta (n^3)$ (I used master theorem) and I tried to show that $T(n) \leq cn^3$. But, when i substitute i got $T(n) \leq c \frac{n^3}{2} + n^3$ and that's it not the exact form of the guess, so it doesn't work. How can I solve this recurrence? Thanks.