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.

  • 3
    $\begingroup$ If you think it might be $n \log n$ you can go ahead and test that with the substitution method. What happens when you try that? You can add your work to original post and can help guide you more. $\endgroup$
    – ryan
    Apr 6, 2019 at 16:02
  • $\begingroup$ Have you read one or more answers in the search result? Have you read this one and this one? $\endgroup$
    – John L.
    Apr 6, 2019 at 16:45


Browse other questions tagged or ask your own question.