Big O Notation – Proper Rules for Identifying Algorithm Complexity

There are several reasons, but probably the most important one is that constants are a function of the implementation of the algorithm, not the algorithm itself. The order of an algorithm is useful for comparing algorithms irrespective of their implementation.

The actual runtime of a quicksort will typically change if it's implemented in C or Python or Scala or Postscript. The same applies for bubble sort -- the runtime will vary widely based on implementation.

However, what will not change is the fact that, all else being equal, as the dataset gets larger the time required to run a bubble sort will increase faster than the time required to run quicksort in the typical case, no matter what language or machine they're implemented with, assuming a reasonably correct implementation. This simple fact allows you to make intelligent inferences about the algorithms themselves when concrete details are not availble.

The order of an algorithm filters out factors that, while important in actual real-world measurements, tend to just be noise when comparing algorithms in the abstract.

The first one looks linear to me; given an input array, a result array twice as large is created, and then every element of the input is traversed to produce two elements of the result. Assuming constant access time for arrays in Java (which is true) and constant array/list length checking (also true AFAIK), given N input elements, all N input elements are traversed, 3N input accesses are made, and 2N assignments are made. This is O(N) plain and simple; if this was the code from the test and you said O(N), you are right and your prof is wrong. The fact that there are multiple steps happening for each iteration of the loop is immaterial; it's not an O(NlogN) function just because each element is accessed three times and the list happens to have 1000 elements.

The second one also appears linear. Given an input collection, the loop traverses half of it, and swaps each of those elements with the "mirrored" element on the other half (basically reversing the collection). Again, neither the fact that 3 reads/writes are made to list elements, nor the fact that only half the items are traversed by the outer loop, makes this a logarithmically-based algorithm; it, like the first, is O(N)-complexity, provided that the collection is constant-time to access.

In fact, I cannot see any way that either of these would be O(logN). Both of them might be O(NlogN), if there's something you're not telling us; that the input collection which you are showing us as an array is actually a Map, using a red-black tree for its internal structure and thus providing log(N) access time. Then the complexity of both of these would be O(NlogN), because for each of the elements traversed by the loop, you spend some constant multiple of logN time reading or writing to elements of the collection.

However, if the problems are exactly as you have stated, your prof is wrong, you are right, and you should make a stink about it to him and to anyone above him that you can get to care, depending on how much of your grade this test represents.

EDIT FROM UPDATE: OK, now we see that the prof marked the wrong two questions wrong:

public static void mystery3(List<String> list) {
   for (int i = 0; i < list.size() – 1; i += 2) {
      String first = list.remove(i);
      list.add(i + 1, first);
   }
}

This one basically swaps each pair of elements; it does so by removing and then re-adding each element to a mutable List collection. Now, if it were a true swap, with a temp variable like you'd use with an array, it would indeed be linear. However, with a List, when you remove or add items in the middle of the collection, the List class automatically rearranges the existing items in the array that it uses behind the scenes to store the elements, by "shifting" each element above the removed element to the next lower index. A removal of element in index X from a collection of N elements will result in N-(X+1) shifts. Same thing in reverse when an element is inserted in between two existing elements; the existing elements to the right of the insertion point are each shifted one place further right to make room.

So, for N elements, it performs N/2 traversals, but N inserts/removals, each of which results in N-(X+1) shifts. As X will, at some point, have the value of every index in the list, this produces a triangular number of total value assignments, N(N-1)/2, which makes it O(N²) complexity. This is a very common breakdown for a quadratic-complexity algorithm; for each index, do something with each higher (or lower) index. Most of the quadratic sorts (e.g. SelectionSort, InsertionSort, BubbleSort) behave in this general way.

public static void mystery4(List<String> list) {
   for (int i = 0; i < list.size() – 1; i += 2) {
      String first = list.get(i);
      list.set(i, list.get(i + 1));
      list.set(i + 1, first);
   }
}

This one performs a similar pair-swapping operation on the elements of the List. However, this implementation is a true "temp swap" as mentioned above. The algorithm swaps pairs, but does so without changing the number of elements in the List; instead, a simple variable first is used to store the variable that is then overwritten in its current position in the List. So, for N/2 traversals, 2N reads/writes are performed, making this algorithm, which does exactly the same thing as the previous one, linear instead of quadratic.

Now, you said you marked this as linear. That's the right answer. Where it might not seem so (and this will be important elsewhere) is that strings in Java are immutable. Once created, they're never changed "in-place"; if the value of a string is modified, it results in the creation of a new String object in memory, and the old one, if nothing else references it, is orphaned for the garbage collector to deal with. So, the modification of a String is an operation linearly time-bound to the total number of characters in the string, because each of those characters must be copied from its current location into the proper new location in the new String. If that were happening, then this would be a linear operation of linear operations, producing a quadratic total time-complexity.

However, that's not happening in this algorithm. Java Strings are also "reference types", meaning that in an assignment of a string from one variable to another (including elements of an array), without any modification, the string is not "cloned"; the memory reference to the string, which is basically a number, is copied between the two variables, and both of them point to the new value. So, the swapping being done is only rearranging these "pointers" actually contained in the array, not creating and deleting the actual strings in memory. That's a constant-time operation, so the dominant term for the Big-Oh notation remains linear.