algorithm - Calculating Big O running time -

algorithm - Calculating Big O running time -

hello having problem finding running time algorithm next assumptions s = o(logn) , running time of random_integer constant time:

1 express n-1 2^t * u u odd: 2 <-- s 3 <-- random_integer(2, n-2); 4 if euclidgcd(a, n) not equal 1 5 homecoming false; 6 x sub 0 <-- a^u mod n; 7 j <-- 1 t 8 x sub j <-- x^2 sub j-1 mod n; 9 if x sub j = 1 , x sub j-1 not equal 1 , x sub j-1 not equal n -1 10 homecoming false; 11 if x sub t not equal 1 12 homecoming false; 13 homecoming true;

starting inner loop exponential modulous operation takes n^3 time , loop runs n iterations giving total of n^4. working way outter loop, have exponential modulous operation takes 1 time again n^3 time , euclidgcd take n^3 time. outter loop runs n iterations. believe these values right but, im confused how total running time. i'm confused on if these 2 nested loops running time should multiplied , if method phone call extendedeuclid within outer loop should multiplied running time outter loop. hope clear help.

the inner loop n^4 (the slowest part within outer loop) , runs 1 time every iteration of outer loop, edit: logn times, n^4logn.

however...

depending on how return false reached early, may n^5 in worst case, e.g. if of time homecoming false on first iteration you've spent n^3-n^4 of work, you'd have average of o(n^3) or o(n^4) (depending on return false was) instead.

algorithm big-o