Problems Calculating Big-O Complexity

I’m a complete beginner to Java, only in my second quarter of classes. I’m having trouble understanding our current chapter about calculating big-O for methods. So I thought I was right in saying that the big-O for these two methods is simply O(N), since there is only one loop that loops through the entire list, but apparently they’re either O(NlogN) or O(logN). I really can’t see why. Can anyone help me understand?

public static int[] mystery1(int[] list) {
    int[] result = new int[2 * list.length];
    for (int i = 0; i < list.length; i++) {
        result[2 * i] = list[i] / 2 + list[i] % 2;
        result[2 * i + 1] = list[i] / 2;
    }
    return result;
}

public static void mystery2(int[] list) {
    for (int i = 0; i < list.length / 2; i++) {
        int j = list.length – 1 – i;
        int temp = list[i];
        list[i] = list[j];
        list[j] = temp;
    }
}

These aren’t homework problems, they were on a test I just took and miserably failed since there were only 4 questions and these two were wrong. I just want to understand why these two aren’t O(N) complexity (professor won’t give out the answers since someone hasn’t done the test yet).

_{These questions were taken straight from the book for the test… which is why I was confident I was right since I had done them already. It was a multiple choice test, and the only options were a)O(1) b)O(N) c)O(logN) d)O(NlogN).}

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.

Filed under: softwareengineering - @ 20:29

Thẻ: big-o, complexity

Thiết kế website giá rẻ

Danh mục

Problems Calculating Big-O Complexity