Question

Big-O notation for each

public static double accumulate (double[] a) { double sum = 0.0; for (int i = 0; i < a.length; i++) sum += a[i]; return sum; } public static double innerProduct(double[] a, double[] b) { // assume a. length == b.length double sum = 0; for (int i = 0; i < a.length; i++) sum += a[i] * b[i]; return sum; } public static int twoSum(int[] a) { int count = 0; for (int i = 0; i < a.length; i++) for (int j = i + 1; j < a.length; j++) if (a[i] + a[j] == 0) count += 1; return count; } public static int twoSumFastUnique (Integer[] a) { Arrays.sort(a); int count = 0; for (int i = 0; i < a.length; i++) { int idx = ArrayUtils.upperBound(a, i+1, a. length, -a[i]); if (idx != a.length && a[idx] == -a[i]) count++; } return count; }

Answer 1

SOL:

1) The time complexity is O(a.length)

if we consider a.length =n

Then Big-O is O(n)

Explanation:

The Loop runs from O to a.length . so the no of iterations will be a.length

The time complexity is directly propotional to number of iterations

No of iterations will be a.length

if we consider a.length = n

So Big-O is O(n)

2) The time complexity is O(a.length)

if we consider a.length =n

Then Big-O is O(n)

Explanation:

The Loop runs from O to a.length .so the no of iterations will be a.length

The time complexity is directly propotional to number of iterations

No of iterations will be a.length

if we consider a.length = n

So Big-O is O(n)

3) The time complexity is O(n²) i.e Big-O is O(n²) if we consider a.length =n

Explanation:

The time complexity is directly propotional to number of iterations

For i=1 The no of iterations will be n-1 times

For i=2 The no of iterations will be n-2 times

for i=3 The no of iterations will be n-3 times

So the no of iterations will be

n-1+n-2+n-3+...+1

=n(n+1)/2

= n²+n/2

= O(n²)

4) The time complexity is O(a.length)

if we consider a.length =n

Then Big-O is O(n)

Explanation:

The Loop runs from O to a.length . so the no of iterations will be a.length

The time complexity is directly propotional to number of iterations

No of iterations will be a.length

if we consider a.length = n

So Big-O is O(n)