CODEWITHSUNDEEP
javafor-loopwhile-looptime-complexity
Michael Bistritzki
Michael Bistritzki

Reputation: 15

Finding the time complexity of this method

I am trying to figure out the time complexity of this code.

My last conclusions about the sections is that the 'while' section the O(logn) the outer for loop must be under 100 so its O(1) and the inner for loop is O(logn) so i think that the time complexity here is O(logn) in the worst case but i am not sure.

public void foo (int n, int m) {
    int i = m;

    while (i > 100) {
        i = i/3;
    }

    for (int k=i ; k>=0; k--) {
        for (int j=1; j<n; j*=2) {
            System.out.print(k + "\t" + j);
        }

        System.out.println();
    }
}

Upvotes: 1

Views: 97

Answers (1)

amrender singh
amrender singh

Reputation: 8239

Lets break your code step by step :

The first loop i.e, 

 while (i > 100)  
     i = i/3;

runs O(logm) times.

for (int k=i ; k>=0; k--) { 
        for (int j=1; j<n; j*=2) {
            System.out.print(k + "\t" + j); 
        } //end inner for loop
        System.out.println(); 
    }

The outer loop can run atmost 100 times, and the inner loop i.e

for (int j=1; j<n; j*=2) {
      System.out.print(k + "\t" + j); 
} //end inner for loop

executes logn times.

total time complexity of for loops = 100logn - > ignoring constants - > logn

Therefore, the complexity is O(log(m)) + O(log(n))

Upvotes: 2

Related Questions