Search code examples
javabig-oanalytics

number of times a statement gets executed in terms of n

I want the true way to get the number of times that a statement in my code gets executed in terms of n.

For example: in this code, how many times do MyStatement1 and MyStatement2 get executed, and why?

sum = 0;
for (i=1; i<=n; i*=2) {
    for (j=1; j<=i; j++) {
        sum++; // MyStatement1
    }

    for (k=1; j<=n; k++) {
        sum++; // MyStatement2
    }
}
Solution

  • MyStatement1: O(n)

    Precise number of executions is based on sum of geometrical progression. The outer loop will be executed m times where 2^m = n thus m = log2(n)

    the inner loop will be executed 1 + 2 + 4 +... + 2^m times. That's a sum of a geometrical progression:

    (1-2^m)/(1-2) = O(2^m) = O(2^log2(n)) = O(n)

    MyStatement2: infinity

    at the time of execution of the 2nd inner loop j=log2(n). Since that is less than n the condition will never be satisfied ending up as an infinite loop.