Time complexity for while loops using modulo

Question

I need help with finding out the time complexity of the first and second loop(the nested for-while loop), I'm not so sure of my answers:

for the first loop: O(log n)

for the second loop: O(sqrt(n) logn)

The Code:

public static int findLength(int n){

        int length = 0;
        //FIRST LOOP
        while (n%2==0){
            length++;
            n /= 2;
        }

        //SECOND LOOP
        for (int i = 3; i <= Math.sqrt(n); i+= 2) {

            while (n%i == 0) {
                length++;

                n /= i;

            }
        }


        if (n > 2)
            length++;

          return length;
    }

score 2 · Accepted Answer · answered Aug 07 '18 at 12:32

2

FIRST LOOP

First Extreme: n is odd
- loop doesn't run
- Time: O(1)
Second Extreme: n is power of 2
- loop runs maximum no of times (with respect to different values of n)
- Time: O(log n)

Overall time complexity: O(log n)

SECOND LOOP

First Extreme: n is prime
- Nested while loop doesn't run at all
- Time: O(sqrt(n))
Second Extreme: n = (p1 ^ q1) * (p2 ^ q2) * .. * (pn ^ qn), where p1, p2 .. pn are primes (generalization of first extreme)
- Total number of operations (excluding loop counters / test expressions): q1 + q2 + ... + qn
- Time: O(log n)

Overall time complexity: O(sqrt(n))

answered Aug 07 '18 at 12:32

y2k-shubham

10,183
11
55
131

2

Note that above analysis assumes that the value `Math.sqrt(n)` is **cached by optimizer** and not evaluated in every *iteration*. Otherwise the complexity would be `O(sqrt(n) * log n)` like you figured (because [`Math.sqrt(n)` takes `log(n)` time](https://stackoverflow.com/questions/23103847/what-is-the-time-complexity-of-the-following-function)) – y2k-shubham Aug 07 '18 at 12:41
may i ask why you excluded the loop increments and test expressions in the outer for loop? but thank you for the explanation i really understood it. peace – aocmonitor Aug 08 '18 at 05:30
my guess is that when the INNER loop doesn't run, the steps taken by the OUTER loop will only be taken into account, but when the INNER loop runs, only the number of steps of the innermost loop would be taken into account even though the INNER loop may not run at some iterations of the OUTER loop – aocmonitor Aug 08 '18 at 05:36
1

In asymptotic analysis of run-time (or space) of a piece of code, we are only interested in determining the amount of time (or space) spent on the **real work**. Loop counters / test expressions are therefore left out. It is even common to ignore overhead of recursive calls. But even if you consider them, the **result won't change** [increment, assignment & comparison are O(1); modulo % is O(no-of-digits) = O(log n), which becomes O(1) for numbers having fixed no of bits]. So it just eases the task at hand without affecting the result (Asymptotic analysis already relies on **approximation**) – y2k-shubham Aug 08 '18 at 05:46

Time complexity for while loops using modulo

1 Answers1