Question

Prove Big O in terms of nₒ and C? There are 5 examples:

class Exercise {
public static int example1(int[] arr) {
int n = arr.length, total = 0;
for (int j=0; j < n; j++) // loop from 0 to n-1
total += arr[j];
return total;
}

public static int example2(int[] arr) {
int n = arr.length, total = 0;
for (int j=0; j < n; j += 2) // note the increment of 2
total += arr[j];
return total;
}

public static int example3(int[] arr) {
int n = arr.length, total = 0;
for (int j=0; j < n; j++) // loop from 0 to n-1
for (int k=0; k <= j; k++) // loop from 0 to j
total += arr[j];
return total;
}

public static int example4(int[] arr) {
int n = arr.length, prefix = 0, total = 0;
for (int j=0; j < n; j++) { // loop from 0 to n-1
prefix += arr[j];
total += prefix;
}
return total;
}

/** Returns the number of times second array stores sum of prefix sums from first. */
public static int example5(int[] first, int[] second) { // assume equal-length arrays
int n = first.length, count = 0;
for (int i=0; i < n; i++) { // loop from 0 to n-1
int total = 0;
for (int j=0; j < n; j++) // loop from 0 to n-1
for (int k=0; k <= j; k++) // loop from 0 to j
total += first[k];
if (second[i] == total) count++;
}
return count;
}

}

Actual big o representation

Ex1: Loop runs from 0 to n, hence linear O(N)
Ex2: Loop runs from 0 to n for n/2 times; but as we ignore constant terms, hence linear O(N)
Ex3:
For j = 0, inner loop runs 1 times.
For j = 1, inner loop runs 2 times.
..
For j = n, inner loop runs n times.

If we sum this, it comes to be n(n+1)/2, which is O(N^2) after ignoring constant terms.

Ex4:
The loop runs n times only. Hence O(N).

Ex5:
The 2 inner loops are same as Ex3, Hence their complexity is O(N^2), and the outer loop runs these inner loop N times, Hence total complexity becomes O(N^3)

Answer 1

class Exercise {
public static int example1(int[] arr) {
int n = arr.length, total = 0;
for (int j=0; j < n; j++) // loop from 0 to n-1
total += arr[j];
return total;
}

Answer: O(n)

Explanation: Here, for loop is executed for n times for each value of j.

Hence, the time complexity is n + k (where k is a positive constant)

Hence, for c = 2 and n0 = 1,

0 <= n + k <= 2n => Time complexity = O(n)

public static int example2(int[] arr) {
int n = arr.length, total = 0;
for (int j=0; j < n; j += 2) // note the increment of 2
total += arr[j];
return total;
}

Answer: O(n)

Explanation: Here, the possible values for j are: 0, 2, 4, ...., n. Here, the for loop is executed n/2 times.

Hence, the time complexity is n/2 + k (where k is a positive constant)

Hence, for c = 1 and n0 = 1,

0 <= n/2 + k <= n => Time complexity = O(n)

public static int example3(int[] arr) {
int n = arr.length, total = 0;
for (int j=0; j < n; j++) // loop from 0 to n-1
for (int k=0; k <= j; k++) // loop from 0 to j
total += arr[j];
return total;
}

Answer: O(n²)

Explanation:

The number of times the for loop is executed is given as:

0 + 1 + 2 + 3 + .... + n-1 (For each value of j] = n(n-1)/2 = (n² - n)/2

Hence, the time complexity is (n² - n)/2 + k (where k is a positive constant)

Hence, for c = 1 and n0 = 1,

0 <= (n² - n)/2 + k <= n² => Time complexity = O(n²)

public static int example4(int[] arr) {
int n = arr.length, prefix = 0, total = 0;
for (int j=0; j < n; j++) { // loop from 0 to n-1
prefix += arr[j];
total += prefix;
}
return total;
}

Answer: O(n)

Explanation: Here, the possible values for j are: 0, 1, 2, ...., n. Here, the for loop is executed n times.

Hence, the time complexity is n + k (where k is a positive constant)

Hence, for c = 2 and n0 = 1,

0 <= n + k <= 2n => Time complexity = O(n)

NOTE: As per Chegg policy, I am allowed to answer only 4 questions (including sub-parts) on a single post. Kindly post the remaining questions separately and I will try to answer them. Sorry for the inconvenience caused.