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$

  • 1
    $\begingroup$ Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – FrankW Jun 3 '14 at 13:57
  • $\begingroup$ Please refer to our reference questions for general material that will help you with these kinds of questions. $\endgroup$ – 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.

Your first question, whether your analysis is correct, can't be answered with certainty until you describe in more detail how you compute modular addition, multiplication, and inverse.

| cite | improve this answer | |
  • $\begingroup$ Mr Rick Decker. Do you mean that two algorithms hava the same growth rate = $O{log n})^3$ $\endgroup$ – Mhsz Jun 3 '14 at 17:08
  • $\begingroup$ @mhsz, exactly. They are both bounded above by some constant multiple of $(\log n)^3$. $\endgroup$ – Rick Decker Jun 3 '14 at 17:11
  • $\begingroup$ But when I draw curve for two equation I note the first time take time greter than second time because coefficient large . Can say that. $\endgroup$ – Mhsz Jun 3 '14 at 17:24
  • 1
    $\begingroup$ @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)$. $\endgroup$ – Rick Decker Jun 3 '14 at 17:34
  • $\begingroup$ Mr Rick Decker thank you very much. now I understand. $\endgroup$ – Mhsz Jun 4 '14 at 18:48

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.