Consider the following algorithm and find the tightest Big-$O$:

enter image description here

Assume $\texttt{multiplyKS}$($A,B$) is $O(n^{1.58})$ and $\texttt{Add}($A,B$)$ is $O(n)$.

If my runtime is $T(n)$, I have:

  1. Lines 1 through 2 is $T(0)=d$, where $d$ is some constant
  2. Line 3 is $T(n/2)$
  3. Line 4 is $cn^{1.58}$, where $c$ is some constant
  4. I ignore lines 5 through 6 because they are negligible, long term
  5. Lines 7 through 8 is $kn$, where $k$ is some constant

Then I have:


After some research, I found that I can simplify (?) my runtime, by def. of Big-$O$, to:


Have I done this correctly? If so, does this imply that I can use the Master Theorem to find Big-$O$?

| cite | improve this question | | | | |
  • 1
    $\begingroup$ I'm not sure what you mean by "runtime of a recurrence". I think what you mean is "solution of the recurrence". The recurrence measures the runtime of an algorithm. $\endgroup$ – Yuval Filmus Feb 16 '19 at 5:33
  • $\begingroup$ You are claiming that $cn^{1.58} + kn = cn^{1.58}$, but this is plainly false. What is correct is that $cn^{1.58} + kn = O(n^{1.58})$. $\endgroup$ – Yuval Filmus Feb 16 '19 at 5:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.