CODEWITHSUNDEEP
javabig-o
hamid
hamid

Reputation: 2079

Confused about Big O notation

I have two questions:

public static void method1(int[] a, int[] b) {
   int sum1 = 0, sum2 = 0;

   for(int i = 0; i < a.length; i++) {
      sum1 += a[i];
   }

   for(int i = 0; i < b.length; i++) { 
      sum2 += b[i];
   }
}

Question 1: Is this in O(n)? Does it matter how many loops (not nested loops) are in method1?

Question 2: What if there is a

Arrays.sort(a);

inside the method1, what function is it?

Upvotes: 8

Views: 293

Answers (2)

NPE
NPE

Reputation: 500437

Question 1: Is this in O(n)?

That's correct (here, n denotes the length of each of the two arrays).

Does it matter how many loops (not nested loops) are in method1?

It doesn't, as long as the number of loops is fixed, and the number of iterations in each loop is linear in n. More formally, if C is some constant, C*n is O(n).

Question 2: What if there is a Arrays.sort(a);

Sorting is usually O(n logn), and this is what Arrays.sort(int[]) does on average. The documentation is vague about the worst-case performance:

This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

This clearly stops short of guaranteeing O(n logn) in the worst case. Reading between the lines suggests that it's probably O(n^2).

It is interesting to note that in JDK7, Arrays.sort(Object[]) uses a different algorithm to the one used by Arrays.sort(int[]). The former is an adaptation of TimSort, and should therefore guarantee O(n logn) worst-case performance. Unfortunately, the documentation again stop short of spelling this out.

Upvotes: 7

Nir Alfasi
Nir Alfasi

Reputation: 53535

  1. a. It's O(n) where n = length of input (total)
    b. Yes it matters how many loops are there: if it's a constant number of loops k then it's O(k*n) which is usually considered as O(n) but if k >= n it's something that should be taken into account

  2. Arrays.sort(a); is implemented using merge sort which is running in O(n log n) both in average and worst case (not like NPE said!).

Update for MrSmith42:

From http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html:
the algorithm used by sort(Object[]) does not have to be a MergeSort, but it does have to be stable.)

And also:

Implementation note: The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

Upvotes: 1

Related Questions