Time complexity of the simple java code

Question

How to determine time complexity of this code ? I guess that modPow method is the most "expensive ".

import java.math.BigInteger;    
public class FermatOne    
{    
    public static void main(String[] args)    
    {    
         BigInteger a = new BigInteger ("2");    
         BigInteger k = new BigInteger ("15");    
         BigInteger c = new BigInteger ("1");    
         int b = 332192810;    
         BigInteger n = new BigInteger ("2");    
         BigInteger power;    
         power = a.pow(b);    
         BigInteger exponent;    
         exponent = k.multiply(power);    
         BigInteger mod;    
         mod = exponent.add(c);    
         BigInteger result = n.modPow(exponent,mod);    
         System.out.println("Result is  ==> " + result);    
     }    
}

Answer 1

Well this particular code deterministically runs in O(1).

However, in more general terms for arbitrary variables, multiply() will run in O(nlog n) where n is the number of bits.

pow() method will run in O(log b) for small a and b. This is achieved by exponentiation by squaring. For larger values, the number of bits gets large (linearly) and so the multiplication takes more time. I'll leave it up to you to figure out the exact analysis.

I'm not 100% about the details about modPow(), but I suspect it runs similarly to pow() except with the extra mod at each step in the exponentiation by squaring. So it'll still be O(log b) multiplications with the added benefit that the number of bits is bounded by log m where m is the mod.

Answer 2

tskuzzy is correct.

But maybe reading between the lines a bit, and assuming this is a homework question, they probably want you to realize that there are several operations happening in this method with varying complexities. And then they probably want you to realize that the complexity of the overall method is the same as whatever the most complex operation is that happens in the method.