CODEWITHSUNDEEP
algorithmbig-o
Rizwan Chaudry
Rizwan Chaudry

Reputation: 179

Calculating Big O running time

Hello I am having trouble finding the running time for this algorithm with following assumptions that s = O(logN) and the running time of Random_Integer is constant time:

  1  express N-1 as 2^t * u where u is odd:
  2  for i <-- to s do
  3    a <-- Random_Integer(2, N-2);
  4    if EuclidGCD(a, N) not equal to 1 then
  5         return false;
  6    x sub 0 <-- a^u mod N;
  7    for j <-- 1 to t do
  8        x sub j <-- x^2 sub j-1 mod N;
  9    if x sub j = 1 and x sub j-1 not equal to 1 and x sub j-1 not equal to N -1 then
  10        return false;
  11   if x sub t not equal to one then
  12        return false;
  13 return true;

Starting from the inner loop the exponential modulous operation takes n^3 time and the loop runs for n iterations giving a total of n^4. Then working my way to the outter loop, we have another exponential modulous operation which takes again n^3 time and then the EuclidGCD also take n^3 time. Finally the outter loop also runs for n iterations. I believe that these values are correct but, im confused as to how I get a total running time. I'm also confused on if these two nested loops running time should be multiplied together and if the method call for ExtendedEuclid within the outer loop should be multiplied with the running time for the outter loop. I hope this is clear thanks for any help.

Upvotes: 2

Views: 488

Answers (1)

Patashu
Patashu

Reputation: 21793

The inner loop is n^4 (the slowest part inside the outer loop) and runs once for every iteration of the outer loop, which is EDIT: logn times, so n^4logn.

HOWEVER...

Depending on how often return false is reached early, it may only be n^5 in the worst case, e.g. if almost all of the time you return false on the first iteration then you've only spent n^3-n^4 of work, so you'd have an average of O(n^3) or O(n^4) (depending on which return false it was) instead.

Upvotes: 1

Related Questions