[Solved] What is the Big Oh gonna be for this algorithm?

Is this a class assignment? I have a feeling you’re asking us to do your homework for you.

The short answer is that the algorithm is O(n^3).

The value of n is read from the console.

The outer loop is i = 1 .. n (i is only ever incremented in the loop, i.e. no steps are skipped).

The second loop is j = 1 .. i (j is only ever incremented in its loop, i.e. no steps are skipped).

The innermost loop, at least in the case where (j % 3 == 0) is k = 1 .. n / 2.

So there are ~n^3 steps required to implement this algorithm.

The fact that j goes from 1 .. i means that, on average, j = 1 .. n/2, making the i/j loops require (1 / 2) * n^2 steps, which is still O(n^2).

The fact that the innnermost loop takes n / 2 steps only in the case where (j % 3 == 0) means that it takes, on average, (1 / 3) * (n / 2) steps, or (1 / 6) * n steps.

Combined with the outermost two loops that’s (1 / 12) * n^3 steps, which is an O(n^3) algorithm.