runtime complexity for while and nested for combined

Question

can someone please help me figure out the runtime complexity of:

public void f(int m,int n){
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.println(k + "/t" + j);
    }
    System.out.println();
}

}

the while part I just really dont know how to approach... the nested loop in my opinion is o(in) because the outer loop runs i times and the inner loop runs n/2 times, but i got the feeling im wrong. if you could tell me how you got t the answer and how to approach questions like this thanks

score 0 · Answer 1 · edited May 23 '17 at 12:29

No, the nested for loop has a run time of O(i*logN) because we are multiplying j every iteration instead of +. i is a constant value smaller than 100

so the total runtime of the nested for loop is

O(i * logN) <= O(100 * logN) = O(logN)

How many times does the while loop run? Similarly, every iteration it's divided by 3, so the total run time of the while loop is O(logM) (the base is a constant so it doesn't matter, see Big O notation Log Base 2 or Log Base 10).

As a result, this function's runtime complexity in Big O notation is O(logM + logN)

runtime complexity for while and nested for combined

1 Answers1