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

Question

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 .

Answer 1

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.