# Finding runtime of a recurrence relation with a fractional power

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

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:

$$T(n)=T(n/2)+cn^{1.58}+kn$$

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

$$T(n)=T(n/2)+cn^{1.58}$$

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

• 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. – Yuval Filmus Feb 16 at 5:33
• 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})$. – Yuval Filmus Feb 16 at 5:34