What is the Big-O for the following function?

Question

void algo(int n, int x) {
for (int k = 0; k < n; ++k)
if (x < 99) {
for (int i = 0; i < n; ++i)
for (int j = 0; j < i; ++j)
System.out.println(”x = ” + x);
} else {
System.out.println(”x = ” + x);
}
}

a. O(n^3)
b. O(n log n)
c. O(n)
d. O(n^2)

Answer 1

a. O(n^3)
The two arrays are traversed by the parameter n, and the outer loop traverses the array from I to n; so O(n) * O(n^2), giving us O(n^3).