determine the time complexity in Java

Question

public class complexity {
    
    public int calc(int n) {
        int a = 2 * Math.abs(n);
        int b = Math.abs(n) - a;
        int result = n;
        for (int i = 0; i < a; i++) {
            result += i;
            for (int j = 0; j > b; j--) {
                result -= j;
            }
            for (int j = a/2; j > 1 ; j/=2) {
                System.out.println(j);
            }
        }
        int tmp = result;
        while (tmp > 0) {
            result += tmp;
            tmp--;
        }
        return result;
    }
    
    
}

I have been given the following program in Java and need to determine the time complexity (Tw(n)).

I checked those site:

Big O, how do you calculate/approximate it? How to find time complexity of an algorithm

But I have still problem too understand it.

Here is the given solution by the professor.From the for loop on I didn't understand anything how he came up with the different time complexity. Can anybody explain it ?

score 2 · Accepted Answer · answered Feb 27 '21 at 23:01

let's go over it step by step :

before the for loop every instruction is executed in a constant time

then:

for(int i = 0; i < a; i++) is executed 2n + 1 times as a = 2*n so 0=> a = 2n steps and the additional step is when i = 2n the program has to execute that step and when it finds that i = 2n it breaks out of the loop.

Now each instruction in the loop has to be executed 2n times (as we are looping from 0 to 2n - 1) which explains why result += i is done 2n times.

The next instruction is another for loop so we apply the same logic about the line for (int j = 0; j > b; j--) : as b = -n this instruction will go from 0 down to -n plus the extra step I mentioned in the first for loop which means : 0 -> -n => n steps + 1 = n+1 steps and as this instruction is in the other loop it will be execited 2n times hence 2n * (n+1)

Instructions inside this for loop are done n times and therefore result -= j is done n times and as the loop itself is done 2n times (result -= j) will be done n*2n times

Same goes for the last for loop except here we are going from a/2 which is n as a = 2n to 1 and each time we are dividing by 2, this is a bit complicated so lets do some steps first iteration j = n then j = n/2 then j = n/4 till j is <= 1 so how many steps do we need to reach 1 ? to reach n/2 we need 1 = log(2) step n => n/2
to reach n/4 we need 2 2 = log(4) steps n => n/2 => n/4 we remark here that to reach n/x we need log(x) steps and as 1 = n/n we need log(n) steps to reach 1 therefore each instruction in this loop is executed log(n) times and as it is in the parent loop it has to be done 2n times => 2n*log(n) times.

for the while loop : result = n + (0 + 1 + 2 + .. + 2n) + (0 + 1 + .. + 2(n^2)) we did this in the for loop and then you do the arithmetic sequence sums it gives result = n^2 (n+1) and here you go.

I hope this is clear don't hesitate to ask otherwise !

score 0 · Answer 2 · answered Feb 27 '21 at 23:00

I am willing to clarify i.e. the last while loop. Unfortunately my answer does not match the professor's. And I am not that certain to have not made a grave mistake.

result starts with n 

for i from 0 upto 2|n|
    result += i

2|n| times done, average i.|n| so result increased by: ~2n.n = 2n².

    for j from 0 downto -|n|
        result -= j

2|n| times done, result increased by: 2n.n/2 = n²

So result is n + 3n²

The outer for loop remains O(n²) as the inner println-for has only O(log n).

The last while loop would be the same as:

for tmp from n + 3n² downto 0
    result += tmp

This is also O(n²) like the outer for loop, so the entire complexity is O(n²).

The result is roughly 3n².3n²/2 or. 4.n⁴.

determine the time complexity in Java

2 Answers2