feynmanium - 2 months ago 10

Java Question

I am having trouble figuring out the time complexity of this code:

`public static void myfun1 (int n) {`

System.out.println("n = " + n);

for (int k = 1; k <= n / 2; k++){

System.out.println(k);

for(int m = 1; m <= k; m++){

System.out.println(k + ", " + m);

}

}

}

public static void main(String[] args){

myfun1(8);

}

When i ran it for n=8, the following was the output:

Output

I am thinking that the first loop will run (n/2) and that I have to multiply it by the inner loop. What I am having trouble with, is the inner loop. Normally I would assume two nested loops are (n^2) but I feel that n/2 in the first loop is correct but I am not sure how the inner loop relates to it. I see that from the output for every k there are k number of loops done my m. For some reason my brain can't translate this relationship in terms of n. Can someone offer me some guidance on this?

Thanks in advance.

Answer

Your inner loop runs 1 time the first time
2 times the second time... up to `n/2`

so it runs like the sum of integers from 1 to `n/2`

= `((n/2+1)*n)/4`

(For 8, it runs 10 times, add a counter to make sure)

So complexity is O(n**2) here.