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);    
     }    
}

Using BigInteger.ONE.shiftLeft(b) is much much faster than a.pow(b); — Peter Lawrey
– Peter Lawrey, Commented Dec 6, 2011 at 17:42
possible duplicate of Big O, how do you calculate/approximate it? — Woot4Moo
– Woot4Moo, Commented Dec 6, 2011 at 18:06

tskuzzy · Accepted Answer · 2011-12-06 17:44:49Z

4

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.

edited Dec 6, 2011 at 17:44

answered Dec 6, 2011 at 17:34

tskuzzy

36.6k15 gold badges78 silver badges145 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Peter Lawrey Over a year ago

It will run the same amount of time, each time it is run.

Freiheit Over a year ago

No that looks serious. The reasons for it are a little over my head, but some code that runs in O(1) would still in in O(1) but it may call code that runs in a different time complexity.

Pedja Over a year ago

@tskuzzy,And what about modPow method ?

Woot4Moo Over a year ago

@pedja perhaps try it yourself?

bigwheels16 · Accepted Answer · 2011-12-06 17:52:33Z

0

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.

edited Dec 6, 2011 at 17:52

answered Dec 6, 2011 at 17:47

bigwheels16

9021 gold badge9 silver badges23 bronze badges

Collectives™ on Stack Overflow

Time complexity of the simple java code

2 Answers 2

4 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related