CODEWITHSUNDEEP
algorithmcomplexity-theory
Pedja
Pedja

Reputation: 373

How can I compare computational complexities : O(k * M(n)) and O(log^6(n))?

Suppose that I have two computational complexities :

  1. O(k * M(n)) - computational complexity of modular exponentiation, where k is number of exponent bits , n is number of digits , and M(n) is computational complexity of the Newton's division algorithm.

  2. O(log^6(n)) - computational complexity of an algorithm.

How can I determine which one of these two complexities is less "expensive" ? In fact notation M(n) is that what confusing me most .

Upvotes: 5

Views: 725

Answers (2)

Raphael
Raphael

Reputation: 10579

First, for any given fixed n, just put it in the runtime function (sans the Landau O, mind you) and compare.

Asymptotically, you can divide one function (resp its Landau term) by the other and consider the quotient's limit for n to infinity. If it is zero, the function in the nominator grows properly, asymptotically weaker than the other. If it is infinity, it grows properly faster. In all other cases, the have the same asymptotic grows up to a constant factor (i.e. big Theta). If the quotient is 1 in the limit, they are asymptotically equal.

Upvotes: 1

Victor Sorokin
Victor Sorokin

Reputation: 12006

Okay, according to this Wikipedia entry about application of Newton method to division , you have to do O(lg(n)) steps to calculate n bits of division. Every step employs multiplication and subtraction, so has bit complexity O(n^2) in case we employ simple "schoolbook" method.

So, complexity of first approach is O(lg(n) * n^2). It's asymptotically slower than second approach.

Upvotes: 0

Related Questions