2

The follow code contains two constructors for a user created Stack Data Structure.

 public class ArrayStack<T> implements BoundedStackInterface<T> {
    protected T[] stack;
    public final int defCap = 100;
    public ArrayStack() {
       stack = (T[]) new Object[defCap];
    }
 }


 public class ArrayStack<T> implements BoundedStackInterface<T> {
    protected T[] stack;
    public ArrayStack(int maxSize) {
       stack = (T[]) new Object[maxSize];
    }
 }

Now in my book the Big(O) of these two constructors is stated to be O(N) but our instructor tried to tell us they should be O(1).

Would someone mind explaining to me why it is O(N) and not O(1)?

Tdorno
  • 1,571
  • 4
  • 22
  • 32

3 Answers3

3

The constructor allocates an amount of memory depending on the length of the array, which is defined as the argument for the constructor. The time it takes to allocate this memory is lineair in the size of the array (and therefore the amount of memory) being allocated, hence O(n). O(1) would mean that the memory can be allocated in a constant amount of time, independent of the size of the array, which is impossible.

Patrick Kostjens
  • 5,065
  • 6
  • 29
  • 46
  • Why does allocating N bytes take time proportional to N? The allocation is normally just a pointer subtraction. – Alan Stokes Oct 26 '13 at 16:10
  • @AlanStokes, I guess I was a little fast assuming memory allocation was a linear allocation, but another SO question (http://stackoverflow.com/questions/282926/time-complexity-of-memory-allocation) has been asked about this topic. From the answers there, I doubt we are going to find a definite answer for this question. – Patrick Kostjens Oct 26 '13 at 16:17
  • Thanks for the link! Yes, I suspect there is no easy answer. – Alan Stokes Oct 26 '13 at 16:39
2

When you ask about big O notation there are two issues to think about:

  1. What is N? (For an n x n matrix, is N n, or n**2?)

  2. What cost are you measuring? A merge sort of N items requires O(N log N) comparisons; but if you are sorting strings the cost of each comparison depends on the lengths of the strings.

For your two constructors, the first allocates O(1) memory, and the second allocates O(N) memory where N is maxSize.

But allocating O(N) memory, or requiring O(N) comparisons, is not at all the same as taking O(N) time - which although clearly important is a much more slippery concept, requiring thinking about the whole system (cache effects, garbage collection, CPU scheduling etc) and not just the algorithm.

In general it seems that it is approximately true that allocating N bytes of memory takes O(N) time, both for classic C-style memory allocation with explicit free and for Java-style garbage collections systems (allocating memory in Java is extremely cheap, but all memory you allocate must be garbage collected, and you have to allow for the amortised cost of that). This is still an interesting research question; Time complexity of memory allocation has some good pointers. (HT to Patrick Kostjens for the link.)

I'm glad you're thinking about this, and not blindly trusting either your book or your instructor.

Community
  • 1
  • 1
Alan Stokes
  • 18,815
  • 3
  • 45
  • 64
1

Memory does not take significantly longer to allocate if you are allocating more of it. There would be an undetectable difference between new Object[100];, new Object[1000];, new Object[100000]; etc. This would indicate that the algorithm you are using to construct the stack is O(1), not O(N).

OldCurmudgeon
  • 64,482
  • 16
  • 119
  • 213
  • What about the cost of garbage collecting the memory? Citation needed ;-) – Alan Stokes Oct 26 '13 at 16:12
  • In Big OH you discuss the algorithm alone - nothing else is considered. – OldCurmudgeon Oct 26 '13 at 17:40
  • You claim "Memory does not take significantly longer to allocate if you are allocating more of it." Why? – Alan Stokes Oct 26 '13 at 18:12
  • @AlanStokes - Claim?? It's a fact! Only if you have less than a terabyte of free memory will the allocation of a terabyte of memory take more time that the allocation of one byte. And in that situation you are analysing the environment, not the algorithm. – OldCurmudgeon Oct 26 '13 at 19:07
  • Have you actually tried it? The first time i wrote a program to allocate 1GB of memory I was surprised by how long it took. See also the question Patrick referred to. – Alan Stokes Oct 26 '13 at 20:00
  • 2
    **In Big OH you discuss the algorithm alone - nothing else is considered** ... not how long it takes - ever!!! Big OH is the **complexity** of the algorithm - nothing more. What is the Big Oh of an algorithm that waits 1000 years then completes? – OldCurmudgeon Oct 26 '13 at 20:31
  • I understand that assertion, although I disagree with it. But your statement that I challenged does not refer to big O notation. – Alan Stokes Oct 26 '13 at 20:39
  • An algorithm that waits 1000 years takes O(1) time - that's easy. – Alan Stokes Oct 26 '13 at 20:40