Consider the following piece of code: public static int method(int[] array, int
ID: 3542412 • Letter: C
Question
Consider the following piece of code:
public static int method(int[] array, int n) {
for (i = 1; i < n; i++)
for (j = 1; j <= i; j++)
if (array[j] < array[j+1])
for (k = 1; k <= n; k++)
array[k] = array[k] * 2;
}
Count the number of basic operations in the above algorithm in the
(a) best case ,
(b) worst case.
Hence state the big-O complexity of the algorithm for both these cases.
Assume that the array index of the first element in the array is 1.
The question is about big-O notation complexity, please show me the work, so i can understand. ty!
Explanation / Answer
Best case is O(n^2) worst case is O(n^3).
The outer 2 loops execute no matter what.
The first loop runs i = 1 to n. It executes n times.
The second loop runs up j = 1 to i. It executes n * (n - 1) / 2 times, which makes it
O(n^2).
The third loop is behind an if sentence. So in best case scenario, it never executes and in worst case scenario it always executes. The third loop executes n times for each execution of second loop.
So O(n^3) is worst case (if evaluates to true every time).
Let's say n is 11;
First loop executes 10 times.
Second loop executes (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10) times which is 10 * 9 / 2 = 45 times.
This is 1/2 * 10^2 - 5 -> O(n^2) since the quadratic function is the biggest.
In case if always evaluates to true, the innermost loop executes:
45 & 10 times = 450 = 1/2 * 10^3 - 50 -> O(n^3), cubic factor being the largest.