8

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?

hamid
  • 2,033
  • 4
  • 22
  • 42
  • 2
    Perhaps this [plain English explanation of Big O](http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o) can help. – syb0rg Mar 16 '13 at 22:07

2 Answers2

7

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.

NPE
  • 486,780
  • 108
  • 951
  • 1,012
  • You're assuming `a` and `b` are the same size – Hunter McMillen Mar 16 '13 at 22:06
  • 3
    @HunterMcMillen This really doesn't matter. Let n be the maximum between a and b. – AndyG Mar 16 '13 at 22:07
  • 1
    @SauceMaster Still important to note. – Hunter McMillen Mar 16 '13 at 22:07
  • He counted individually. For even the second question he isn't even fully correct. Technically the O notation of that method would then be O(n + m + nlog(n) + mlog(m)) assuming both `a` and `b` were sorted. Individually, loop-per-loop he is correct. –  Mar 16 '13 at 22:08
  • Quick sort worst case runs in O(n^2) but it doesn't matter cause in Java `Arrays.sort()` is implementing merge sort which runs in O(n log n) in both cases (average AND worst) – Nir Alfasi Mar 16 '13 at 22:14
  • @alfasin: If you carefully read the documentation, it does not guarantee `O(n logn)` worst-case performance. – NPE Mar 16 '13 at 22:18
  • @NPE you're right but it's worth mentioning that according to literature Quick sort (and its variants) is faster in practice than other O(n log n) algorithms and its worst-case is rare. – Nir Alfasi Mar 16 '13 at 22:40
  • +1 for mentioning the difference between sorting Object[] and int[] in Java 7 – Nir Alfasi Mar 16 '13 at 22:43
1

  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.

Nir Alfasi
  • 53,191
  • 11
  • 86
  • 129
  • So what if the method contains both the loop and `Arrays.sort(a)`? – hamid Mar 16 '13 at 22:13
  • 1
    @Sam it depends if the sort runs inside the loop or not... :) – Nir Alfasi Mar 16 '13 at 22:15
  • @alfasin: Yes you there are sorting algorithm with worst case O(n logn), but the JDK does not use one of them. From the API: *"The sorting algorithm is a tuned quicksort"*. Therefore using Arrays.sort(..) has worst case O(n²). – MrSmith42 Mar 16 '13 at 22:15
  • @MrSmith42 not true, are you sure you're checking the latest version of the documentation ? checkout the update I added for you in the answer. – Nir Alfasi Mar 16 '13 at 22:20
  • 1
    @Sam the running time should take the "worst case" meaning: if the loop runs in O(n) where n = total length of input and there is also a call to sort() which runs in O(n log n) then the total running time of the method should be O(n log n) – Nir Alfasi Mar 16 '13 at 22:23
  • @alfasin: Yes it is still a quicksort which has worst case O(n²), even if it is tuned to have more often O(n logn) than naive quicksort. There is no variant of quicksort that has worst case O(n logn). – MrSmith42 Mar 16 '13 at 22:50
  • @alfasin: As you posted yourself 'This algorithm offers O(n log(n)) performance on **many** data sets...' That is does NOT mean for all, what would be necessary, if you look at the worst case. – MrSmith42 Mar 19 '13 at 15:00
  • @MrSmith42 you're right - and that's why I added the **update** to my question :) with that said, one of my professors said that experimentally quick sort runs faster then merge sort, this is a weird result that no one could explain, and that's why, I believe, quicksort was chosen as the implementation. – Nir Alfasi Mar 19 '13 at 15:14
  • @alfasin: Quicksort is most times faster than merge-sort, because it runs linear through memory and is in place. It is such an elegant and simple algorithm and the worst case is a very very rare one. – MrSmith42 Mar 19 '13 at 20:02
  • @MrSmith42 this might be the intuition, but you know how it works: unless you can provide a legit `proof` that shows why in average the running time of quicksort is better than merge, the academy won't accept it... – Nir Alfasi Mar 22 '13 at 19:05
  • @alfasin: I am sure someone out there have made the proof over all possible permutations of the Input. **;-)** I am satisfied with the intuition and the experience of generations of software developers. – MrSmith42 Mar 22 '13 at 22:31
  • @MrSmith42 you can provide such a proof (all possible permutations) only for a specific input (un-sorted list) when a generic proof should not rely on specific input-set. Obviously it's not possible to generate such a proof for ALL possible inputs. This is another example where exact science meets mystery... :) – Nir Alfasi Mar 22 '13 at 22:53