Got this question on a test that I've been stuck on for a few days regarding Big O time complexity analysis:
Below is the C code:
if ( A > B ) {
for ( i=0; i<n^2/100; i++ ){ //1
for ( j=n^2; j>i; j-- ){ //2
A += B;}}
}
else {
for ( i=0; i<2n; i++ ){ //3
for ( j=3n; j>i; j-- ){ //4
A += B;}}
}
My first instinct was that this algorithm would have a big O of O(n2) with the nested for loops and such but it wasn't a multiple choice answer. Tried to count each loop iteration manually but having trouble accounting for the changing i in each inside loop (2 and 4). Also having trouble trying to write it as a summation.
Consider the first case where A > B. The inner loop executes a number of iterations equal to n^2 - i for each value of i iterated over by the outer loop. Consider n = 2 and i = 1. n^2 = 4 and the inner loop iterates over j = 4, j = 3, j = 2, three iterations, consistent with our finding.
The total number of iterations of the inner loop is therefore the sum of all n^2 - i where i varies from 0 to floor(n^2/100) - 1. Let us define k := floor(n^2/100) - 1. Then this sum is equal to kn^2 - k(k+1)/2. Substituting the expression for which k stands we recover [floor(n^2/100) - 1]n^2 - [floor(n^2/100) - 1][floor(n^2/100)]/2. This is no greater than (n^2/100 - 1)n^2 - (n^2/100 - 1)(n^2/100)/2. We may multiply through to get n^4/100 - n^2 - n^4/20000 + n^2/200 = n^4(1/100 - 1/20000) - n^2(1 - 1/200). From this we can see that the time complexity of the first case is O(n^4). Indeed, it is also Omega(n^4) and Theta(n^4).
In the case where A <= B, the analysis is similar. It is easy to show that the time complexity of the second case is O(n^2), Omega(n^2) and thus Theta(n^2).
Therefore, we may confidently say that:
O(n^4);Omega(n^2);Theta bounds instead.