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)