# Compare runtime for algorithms?

I try to compute the asymptotic runtime for this algorithm and compare it with other algorithm

$A = (C -(D * E ) ) mod p$

$B = ((C * (D)^{-1} - (E * F ))$ mod p if we suppose each value A, B, C, D, E, F has O(log n) bit

My attempts were as follows

line one = $O(\log n)^2$ + log n

line two = $O(\log n)^2$ + $O(\log n)^3$ + $\log n$ + $O(\log n)^2$

Then line one + line two = $O(3\log n)^2 + O(\log n)^3 + log n$

Are attempts were correct or wrong. If it correct. can I say

T(line one + line two) = $O(3\log n)^2 + O(\log n)^3 + log n$

is better than

(Other algorithm) = $O(2\log n)^3$

• Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. – FrankW Jun 3 '14 at 13:57
• Please refer to our reference questions for general material that will help you with these kinds of questions. – D.W. Jan 20 '16 at 17:43

For your second question, whether a runtime of $O(3\log n)^2+O(\log n)^3+\log n$ is better than $O(2\log n)^3$, the answer is "asymptotically speaking, no". The dominant term in the first expression is $O(\log n)^3$ and the second expression is $8(\log n)^3$. Since, roughly speaking, big-O ignores constant multiples, the two expressions are asymptotically equivalent.
• Mr Rick Decker. Do you mean that two algorithms hava the same growth rate = $O{log n})^3$ – Mhsz Jun 3 '14 at 17:08
• @mhsz, exactly. They are both bounded above by some constant multiple of $(\log n)^3$. – Rick Decker Jun 3 '14 at 17:11
• @mhsz. No. You don't know that the coefficient is large, since big-O suppresses constants. As a simple example, consider $f(n) = 300n^2$ and $g(n) = 2n^2$. Both of these are $O(n^2)$, though of course $f(n)\ge g(n)$. – Rick Decker Jun 3 '14 at 17:34