Big theta notation for array and linked list classes

Question

I am trying to determine the complexity metrics (Big-theta notation) for each method and constructor in my classes that create a queue using an array and a linked list as the underlying structures. Specifically, I am not sure how to look at and quickly determine whether each method or constructor is O(k) or O(n). Could someone explain this?

Array class:

public class UnboundedQueueArray<T> implements UnboundedQueue<T> {

  // elements stored in array
  private T[] elements;
  // the number of elements currently in the queue
  private int numElems;

  // initial length of queue
  private static final int INITIAL_LENGTH = 10;

  /**
   * Constructs the UnboundedQueueArray object.
   */
  @SuppressWarnings("unchecked")
  public UnboundedQueueArray() {
    elements = (T[]) new Object[INITIAL_LENGTH];

    numElems = 0;
  }

  /**
   * This method inserts the specified element, unless the
   * queue is full.
   * 
   * @param o The element to be inserted.
   */
  public void insert(T o) {
    // checks and enlarges capacity if necessary
    ensureExtraCapacity(1);

    elements[numElems] = o;
    numElems++;
  }

  // this helper method ensures there is always extra capacity
  // in the queue to insert elements 
  @SuppressWarnings("unchecked")
  private void ensureExtraCapacity(int extraCapacity) {

    if(numElems + extraCapacity > elements.length) {
      // double old capacity
      int newCapacity = elements.length * 2 + extraCapacity;
      // allocate new array
      T[] newElements = (T[]) new Object[newCapacity];
      // copy contents of old array into new array
      for(int i = 0; i < length(); i++) {
        newElements[i] = elements[i];
      }

      // replace old array with new array
      elements = newElements;
    }

  }

  /**
   * This method returns the element at the front of the
   * queue, unless the queue is empty.
   *
   * @return The element at the front of the queue. 
   * @throws EmptyQueueException If the queue is empty.
   */
  public T front() throws EmptyQueueException {
    if(length() == 0) {
      throw new EmptyQueueException("Queue is empty.");
    }

    return elements[0];
  }

  /**
   * This method retrieves and removes the element at the front
   * of the queue, unless the queue is empty.
   * 
   * @return The element at the front of the queue.
   * @throws EmptyQueueException If the queue is empty.
   */
  public T remove() throws EmptyQueueException {
    if(length() == 0) {
      throw new EmptyQueueException("Queue is empty.");
    }

    // retrieve element at front of queue
    T frontElem = elements[0];

    // shift elements to the left
    for(int i = 1; i < length(); i++) {
      elements[i - 1] = elements[i];
    }

    // "null out" last element
    elements[numElems - 1] = null;
    // decrement number of elements
    numElems--;

    return frontElem;
  }

  /**
   * This method reports whether or not the queue contains
   * element(s).
   * 
   * @return If one or more elements exists or not.
   */
  public boolean hasMember() {
    return (length() > 0);
  }

  /**
   * This method returns the current length of the queue.
   * 
   * @return The length of the queue.
   */
  public int length() {
    return numElems;
  }

  /**
   * This method provides a string representation of the queue.
   * 
   * @return The String representation of the queue.
   */
  public String toString() {
    // for empty queue
    if(length() == 0) {
      String str = "[ " + length() + " : ]";
      return str;
    }

    // fencepost algorithm
    String str = "[ " + length() + " : " + elements[0];

    for(int i = 1; i < length(); i++) {
      str += ", " + elements[i];
    }

    str += " ]";

    return str;

  }

}

Linked list class:

public class UnboundedQueueLinkedList<T> implements UnboundedQueue<T> {

  // the reference to the first link
  private Link first;
  // the reference to the last link (if it exists)
  private Link last;

  // the number of links in the queue
  private int numLinks;

  // initial length of queue
  private static final int INITIAL_LENGTH = 10;

  /**
   * Constructs the UnboundedQueueLinkedList object.
   */
  @SuppressWarnings("unchecked")
  public UnboundedQueueLinkedList() {
    first = null;
    last = null;

    numLinks = 0;
  }

  /**
   * This method inserts the specified element, unless the
   * queue is full.
   * 
   * @param o The element to be inserted.
   */
  public void insert(T o) {

    Link newLink = new Link(o, null);

    if(first == null) {
      // we are adding the first link
      first = newLink;
    } else {  // there are existing links, so add newLink after old last link
      last.next = newLink;
    }

    // update the last link
    last = newLink;

    // increment the number of links in the queue
    numLinks++;

  }

  /**
   * This method returns the element at the front of the
   * queue, unless the queue is empty.
   *
   * @return The element at the front of the queue. 
   * @throws EmptyQueueException If the queue is empty.
   */
  @SuppressWarnings("unchecked")
  public T front() throws EmptyQueueException {
    if(length() == 0) {
      throw new EmptyQueueException("Queue is empty.");
    }

    T frontElem;
    // get link at front of queue
    Link frontLink = getLinkAtPos(0);
    frontElem = (T) frontLink.item;

    return frontElem;
  }

  // this helper method gets the link at the specified position
  private Link getLinkAtPos(int pos) {
    Link p = first;

    for(int i = 0; i < pos; i++) {
      p = p.next;
    }

    return p;
  }

  /**
   * This method retrieves and removes the element at the front
   * of the queue, unless the queue is empty.
   * 
   * @return The element at the front of the queue.
   * @throws EmptyQueueException If the queue is empty.
   */
  @SuppressWarnings("unchecked")
  public T remove() throws EmptyQueueException {
    if(length() == 0) {
      throw new EmptyQueueException("Queue is empty.");
    }

    T removedElem;
    removedElem = (T) first.item;
    // remove "first" link
    first = first.next;

    // update "last" if necessary
    if(first == null) {
      last = null;
    }

    // decrement the number of links in the queue
    numLinks--;

    return removedElem;
  }

  /**
   * This method reports whether or not the queue contains
   * element(s).
   * 
   * @return If one or more elements exists or not.
   */
  public boolean hasMember() {
    return (length() > 0);
  }

  /**
   * This method returns the current length of the queue.
   * 
   * @return The length of the queue.
   */
  public int length() {
    return numLinks;
  }

  /**
   * This method provides a string representation of the queue.
   * 
   * @return The String representation of the queue.
   */
  public String toString() {
    // for empty queue
    if(length() == 0) {
      String str = "[ " + length() + " : ]";

      return str;
    }

    Link p = first;
    String str = "[ " + length() + " : " + p.item;

    for(int i = 1; i < numLinks; i++) {
      p = p.next;
      str += ", " + p.item;
    }

    str += " ]";

    return str; 
  }

  // this helper class creates the links that structure the list
  class Link<T> {

    // data associated with this link
    public Object item;
    // next link, or null if no next link
    public Link next;

    /**
     * Constructs the Link object.
     * 
     * @param item The data to be associated with this Link object.
     * @param next The next link (or null if no next link exists).
     */
    public Link(Object item, Link next) {
      this.item = item;
      this.next = next;
    }

  }

}

EDIT: Here is stack array class:

public class UnboundedStackArray<T> implements UnboundedStack<T> {

  // elements stored in array
  private T[] elements;
  // the number of elements currently in the stack
  private int numElems;
  // initial depth of stack
  private static final int INITIAL_DEPTH = 10;

  /**
   * Constructs the UnboundedStackArray object.
   */
  @SuppressWarnings("unchecked")
  public UnboundedStackArray() {
    elements = (T[]) new Object[INITIAL_DEPTH];

    numElems = 0;
  }

  /**
   * This method "pushes" an element onto the top of the stack.
   * 
   * @param o The element to be "pushed" (or added) onto the top
   *          of the stack.
   */
  public void push(T o) {
    // ensure space to add element
    ensureExtraCapacity(1);

    elements[numElems] = o;
    // increment the number of elements in the stack
    numElems++;
  }


  // this helper method ensures there is always extra capacity
  // in the stack to "push" (or add) elements onto top of stack
  @SuppressWarnings("unchecked")
  private void ensureExtraCapacity(int extraCapacity) {

    if(numElems + extraCapacity > elements.length) {
      // double old capacity
      int newCapacity = elements.length * 2 + extraCapacity;
      // allocate new array
      T[] newElements = (T[]) new Object[newCapacity];
      // copy contents of old array into new array
      for(int i = 0; i < depth(); i++) {
        newElements[i] = elements[i];
      }

      // replace old array with new array
      elements = newElements;
    }

  }

  /**
   * This method retrieves the element at the top of the stack,
   * unless the stack is empty.
   * 
   * @return The element at the top of the stack.
   * @throws EmptyStackException If the stack is empty.
   */
  public T top() throws EmptyStackException {
    if(depth() == 0) {
      throw new EmptyStackException("Stack is empty");
    }

    return elements[numElems - 1];
  }

  /**
   * This method retrieves and removes the element at the top of
   * the stack, unless the stack is empty.
   * 
   * @return The element at the top of the stack.
   * @throws EmptyStackException If the stack is empty.
   */
  public T pop() throws EmptyStackException {
    if(depth() == 0) {
      throw new EmptyStackException("Stack is empty");
    }

    // retrieve element at top of stack
    T topElem = elements[numElems - 1];
    // "null out" element at top of stack
    elements[numElems - 1] = null;
    // decrement number of elements
    numElems--;

    return topElem;
  }

  /**
   * This method reports whether or not the stack contains
   * element(s).
   * 
   * @return If one or more elements exists or not.
   */
  public boolean hasMember() {
    return (depth() > 0);
  }

  /**
   * This method returns the current depth (or length) of the stack.
   * 
   * @return The depth of the stack.
   */
  public int depth() {
    return numElems;
  }

  /**
   * This method provides a string representation of the stack.
   * 
   * @return The String representation of the stack.
   */
  public String toString() {
    // for empty stack
    if(depth() == 0) {
      String str = "[ " + depth() + " : ]";
      return str;
    }

    String str = "[ " + depth() + " : " + elements[numElems - 1];

    for(int i = numElems - 2; i >= 0; i--) {
      str += ", " + elements[i];
    }

    str += " ]";

    return str;

  }

}

Here is stack linked list class:

public class UnboundedStackLinkedList<T> implements UnboundedStack<T> {

  // the reference to the first link
  private Link first;
  // the reference to the last link (if it exists)
  private Link last;

  // the number of links in the stack
  private int numLinks;

  // initial length of stack
  private static final int INITIAL_LENGTH = 10;

  /**
   * Constructs the UnboundedStackLinkedList object.
   */
  @SuppressWarnings("unchecked")
  public UnboundedStackLinkedList() {
    first = null;
    last = null;

    numLinks = 0;
  }

  /**
   * This method "pushes" an element onto the top of the stack.
   * 
   * @param o The element to be "pushed" (or added) onto the top
   *          of the stack.
   */
  public void push(T o) {
    Link newLink = new Link(o, null);

    if(first == null) {
      // add the first link
      first = newLink;
    } else {  // there are existing links, so add newLink after old last link
      last.next = newLink;
    }

    // update the last link
    last = newLink;

    // increment the number of links in the queue
    numLinks++;
  }

  /**
   * This method retrieves the element at the top of the stack,
   * unless the stack is empty.
   * 
   * @return The element at the top of the stack.
   * @throws EmptyStackException If the stack is empty.
   */
  @SuppressWarnings("unchecked")
  public T top() throws EmptyStackException {
    if(depth() == 0) {
      throw new EmptyStackException("Stack is empty.");
    }

    T topElem;
    // get link at front of queue
    Link topLink = getLinkAtPos(numLinks - 1);
    topElem = (T) topLink.item;

    return topElem;
  }

  // this helper method gets the link at the specified position
  private Link getLinkAtPos(int pos) {
    Link p = first;

    for(int i = 0; i < pos; i++) {
      p = p.next;
    }

    return p;
  }

  /**
   * This method retrieves and removes the element at the top of
   * the stack, unless the stack is empty.
   * 
   * @return The element at the top of the stack.
   * @throws EmptyStackException If the stack is empty.
   */
  @SuppressWarnings("unchecked")
  public T pop() throws EmptyStackException {
    if(depth() == 0) {
      throw new EmptyStackException("Stack is empty.");
    }

    T removedElem;
    removedElem = (T) last.item;

    Link p = first;
    for(int i = 0; i < depth() - 2; i++) {
      p = p.next;
    }

    //p.next = null;

    last = p;

    // update "last" if necessary
    if(first == null) {
      last = null;
    }

    // decrement the number of links in the queue
    numLinks--;

    return removedElem;
  }

  /**
   * This method reports whether or not the stack contains
   * element(s).
   * 
   * @return If one or more elements exists or not.
   */
  public boolean hasMember() {
    return (depth() > 0);
  }

  /**
   * This method returns the current depth (or length) of the stack.
   * 
   * @return The depth of the stack.
   */
  public int depth() {
    return numLinks;
  }

  /**
   * This method provides a string representation of the stack.
   * 
   * @return The String representation of the stack.
   */
  @SuppressWarnings("unchecked")
  public String toString() {
    // for empty stack
    if(depth() == 0) {
      String str = "[ " + depth() + " : ]";
      return str;
    }

    Link pL = last;
    String str = "[ " + depth() + " : " + pL.item;

    for(int i = numLinks - 2; i >= 0; i--) {
      Link tempLink = getLinkAtPos(i);
      str += ", " + tempLink.item;
    }

    str += " ]";

    return str; 
  }

  // this helper class creates the links that structure the list
  class Link<T> {

    /**
     * Data associated with this link.
     */
    public Object item;

    /**
     * Next link, or null if no next link.
     */
    public Link next;

    /**
     * Constructs the Link object.
     * 
     * @param item The data to be associated with this Link object.
     * @param next The next link (or null if no next link exists).
     */
    public Link(Object item, Link next) {
      this.item = item;
      this.next = next;
    }

  }

}

Answer 1

Array class:

UnboundedQueueArray: O(1)
insert: O(1)
ensureExtraCapacity: O(n) (n = current length)

"O(n) is worst case, O(1) otherwise"

front: O(1)
remove: O(n)

"Always O(n)"

length: O(1)

Optimalization:

I highly recommend you use a stack for this behavior, since it handles each method with O(1) complexity.

Linked list:

UnboundedQueueLinkedList: O(1)
insert: O(1)
The behavior seems to be incorrect

last.next = newLink;
last = newLink;

getLinkAtPos: O(pos)
remove: O(1)
length: O(1)

There are some optimalizations that can be done.

UnboundedQueueLinkedList.getLinkAtPos
If you make this a double-linked list, then you could start at the end if pos > length() / 2. This will reduce worst-case complexity to O(log(n)).

Stack array class:

UnboundedStackArray: O(1)
push: O(1) + ensureExtraCapacity
ensureExtraCapacity: wcs is O(n), bcs is O(1)
top: O(1)
pop: O(1)
depth: O(1)
toString: O(n)

I would definitely not use an array for a stack, a list is much more efficient

Stack linked list:

UnboundedStackLinkedList: O(1)
push: O(1)

Again, it looks like the functionality is incorrect

top: O(1) + getLinkAtPos
getLinkAtPos: O(n)
pop: O(n)
depth: O(1)
toString: O($n^2$)

This could be much more efficient.

If you create a stack, you only have to keep track of the top item. Each time you push, the top item gets replaced by the new item and the next linked item of the new item is the old top. Each time you pop, the top item gets popped and its reference it set as the new top. The only method that would be more than O(1) would be the toString() method.

Answer 2

@user2581779: I'll try to explain what O(n) means, but I will not examine your code. Hopefully, you will be able to answer this (and other related questions) after reading my answer by yourself.

Why Big-O notation?

First of all, you should understand why O-notation is used. You could for example use seconds of execution time on a given computer, right?

Well, this has a lot of problems:

• Even if every programmer / computer scientist had the same computer for executing, the time would vary (because of many factors, e.g. temperature)
• You would have to thing very carefully about your test cases. Let's say you want to examine an algorithm that sorts elements in an array. What do you want to sort (numbers / objects)? How many objects do you want to sort? This might influence the time you measure
• You only get statements for the concrete architecture / system you've tested.

Okay, simply measuring seconds is not a good idea. But why don't you measure number of operations?

• The number of operations might be difficult to determine (How many operations are int a = 7 + 3? How many are a += b? You have to think about compiler optimizations and how the underling assembler would look)

In theory, you're always more interested in how your algorithm develops when you increase the input size.

So, suppose you have an array of n elements. You want to get these elements sorted. Algorithm A needs n^2 + 1234 operations, algorithm B nees n^1.9 + 123123123123123 operations. Which one is better? (Please note that n is only a variable. I could also name it k or whatever)

Quite long, algorithm A will perform better. But as soon as B gets better (with more elements n) it will be MUCH better than A.

So, you can forget about additive constant terms. And also about multiplicative constants. In practice, multiplicative constants might be very important, but Big-O notation skips that out.

Please note that you care about worst cases. Best cases are equally easy to examine, but not interesting.

Average case analysis is difficult to get done right. If you want to try it, search for "accounting method" or "aggregation method".

For what is Big-O notation used?

Space- and time complexity. For most simple applications, only time complexity is important. But please note that you can quite often make a time/space trade-off. When you store more information, your algorithm might be faster.

Big-O notation is only used to get a feeling for how strong a function is growing.

Mathematics

Formally:

Let g : N -> R be a function.

O(g(n)) &:= {f(n) | \exists_{c > 0} \exists_{n_0 > 0} \forall_{n \geq n_0}: f(n) < c *g(n) }

(See my site for a rendered version)

This means, when it is correct to say that your program is in O(n), it is also correct to say it is in O(n^2). Big Theta notation makes this better, but is much more difficult to determine correctly.

How do I get Big-O notation?

For most programs, its quite simple:

• First of all, define the value that is growing (e.g. number of elements you want to sort). This is your n.
• Then take a look at loops.
  • One loop over n means you're at lest in O(n) (it might be worse, though)
  • A nested loop where both variables loop from 0..n means your in O(n^2) or worse
• Take a look at recursive functions. Examine it with Master theorem.
• Take a look at datastructures and functions you call. For many Java datastructures, you can get the big-O time complexity by searching
• Tree-datastructures often have something with log(n) when the tree is balanced, as this is the height of the tree (but only if you can guarantee that it is balanced!)
• You can get the time by analyzing sums. So when you have two nested loops, one from 0..n with running variable i and one from i..n which does one "basic" operation you get sum_{i=0}^n \sum_{j=i}^n 1 = sum_{i=0}^n i = (n^2 + n)/2 + 1. It needs a little bit of practice to determine which operations are 1 and which are n or something different, but as soon as you have written them in a mathematical way, you can use Wolfram|Alpha to simplify them. See my article about Gaussian elimination for an example.

Answer 3

Specifically, I am not sure how to look at and quickly determine whether each method or constructor is O(k) or O(n).

First, go through the code and find all the methods that contain only O(1) code. These methods won't have loops that run n times, and won't call O(n) methods. Since these just run straight through, they are O(1), even if they call many other O(1) methods outside of loops. If the method loops through O(0) code n times, that method is 0(n). If it has multiple O(n) operations that are not inside loops, it's still O(n), though potentially with a larger coefficient of n. If it has O(n) code that is performed n times, it's O(n^2).

Array

UnboundedQueueArray() is O(INITIAL_LENGTH), which is O(1) since INITIAL_LENGTH is constant. ensureExtraCapacity(int extraCapacity) is O(n) whenever it extends the internal array since it declares an array of size newCapacity (which must be greater than n) and runs a loop n times, but is O(1) otherwise.

insert is where things get fun. Roughly every n times it is called, it calls ensureExtraCapacity as an O(n) operation. If you do something O(n) once every n times you are called, you are O(n/n) on average, or O(1). But since you are occasionally O(n), we give this a special name: amortized constant time.

front, hasMember, and length are O(1), remove is O(n) because of the loop, and toString is only O(n) since we can access elements in constant time.

LinkedList

UnboundedQueueLinkedList (the constructor), insert, front, remove, hasMember, and length are all O(1). getLinkAtPos(int pos) could be said to be O(pos), but we just call it O(n) since the worst case gets bigger as n gets bigger.

toString() is O(n^2), because it performs an O(n) operation, getLinkAtPos, n times.

Notes:

If you go back to your original implementation of toString() for the LinkedList, you can get it to go down to O(n) since you avoid calling getLinkAtPos inside the loop.

public String toString() {
        // for empty queue
        if(length() == 0) {
          String str = "[ " + length() + " : ]";

          return str;
        }

        Link p = first;
        String str = "[ " + length() + " : " + p.item;

        for(int i = 1; i < numLinks; i++) {
          p = p.next;
          str += ", " + p.item;
        }

        str += " ]";

        return str; 
      }