Big O notation

March 16th, 2005, 7:04 pm

I've completed the methods of three seperate programs below. In learning about Big O notation, I have to identify which formula each method would use. The concept of Big O is quite confusing to me, but i've given a go at it, and was wondering if anyone could provide some correction/suggestions/advice. Each code block is an individual method, and i've put my answer, as well as why I chose that answer, before each block.

Most importantly I need to see if my answers are way off- but also any tips onto what to look for in code to decide which formula to use would really help.

It looks like a lot of code, but in reality many of the methods are similar and quite short. Any help is greatly appreciated.



Implementing a Resizable Stack

O(n) because it goes trough and array, and depends on the number (n) of things to do.

Line number On/Off

Code: Select all

    public void setCapacity (int capacity) throws IllegalStateException
            Object [] newArray = new Object [capacity];
            for (int i=0; i<top ;i++){
            newArray[i] = array[i];
            }
            array = newArray; 
    }

O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.

Line number On/Off

Code: Select all

    public int getCapacity () {
   return array.length;
    }

O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.

Line number On/Off

Code: Select all

    public int getInitCapacity () {
   return initCapacity;
    }

O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.

Line number On/Off

Code: Select all

    public int getItemCount () {
        return top;
           
    }

O(n) goes through the array so it depends only on n items.

Line number On/Off

Code: Select all

    public void trim () {
        if(top > 0){
            Object [] newArray = new Object [top];
            for (int i=0; i<top ;i++){
                newArray[i] = array[i];
            }
        array = newArray;
        }
        else{
            Object[] newArray = new Object[1];
            array = newArray;
        }
    }

O(n) because it goes trough and array, and depends on the number (n) of things to do.

Line number On/Off

Code: Select all

    public void clear () {
   for (int i=0; i<array.length; i++){
            array[i]=null;
            top=0;
        }       
    }

O(n) because it goes trough and array, and depends on the number (n) of things to do.

Line number On/Off

Code: Select all

    public void reset () {
   array = new Object [initCapacity];
        for (int i=0;i<array.length;i++)
            array[i]=null;
            top=0;
    }

Implementing a Circular Queue


O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.

Line number On/Off

Code: Select all

public void add (Object item) {
       if (isFull()){
            addToCapacity(3);
       }
       array[rear] = item;
       rear = (rear + 1) % array.length;
       itemCount++;
    }

O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.

Line number On/Off

Code: Select all

    public Object remove () throws IllegalStateException {
       Object hold = array[front];
       front = (front + 1) % array.length;
       itemCount--;
       return hold;
    }

O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.

Line number On/Off

Code: Select all

    public boolean isEmpty () {
        return itemCount == 0;
    }

O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.

Line number On/Off

Code: Select all

    public boolean isFull () {
        return itemCount == array.length;
    }

O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.

Line number On/Off

Code: Select all

    public int getItemCount () {
        return itemCount;         
    }

O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.

Line number On/Off

Code: Select all

    public int getCapacity () {
        return array.length;         
    }

O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.

Line number On/Off

Code: Select all

    public int getInitCapacity () {
        return initCapacity;         
    }

O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.

Line number On/Off

Code: Select all

    public void reset () {
        array = new Object[initCapacity];
        itemCount=0;
        front=0;
        rear=0;
    }

O(n) - this depends on n because it is a loop and therefor depends on the number of items. It is two for loops but they are NOT nested so it isn't O(n^2) ( i.e. n squared)

Line number On/Off

Code: Select all

    private void addToCapacity (int increment) throws IllegalStateException {
            Object [] newArray = new Object [array.length+increment];
            for (int i=0; i<rear ;i++){
                newArray[i] = array[i];
            }
            for (int i=front; i<array.length ;i++){
                newArray[i+increment] = array[i];
            }
            front = front + increment;
            array = newArray;           
           
    }

Array Implementation of an Ordered List

O(n) This one is more complicated- and I'm not even sure but i'm going to venture a guess that its O(n) based on the same answer I gave for the previous one.

Line number On/Off

Code: Select all

public void insert (String value) {

//search array from index 0 upwards
        int i = 0;
        for (i = 0; i < itemCount; i++){
            Item curItem = (Item)array[i];
            String curValue = curItem.getValue();
            int result = value.compareTo(curValue);
           
            if (result == 0) {
               curItem.incOccurrences();   
               return;
               
            }
            else if (result < 0){
                break;   
            }
        }   
        // make room
        if (itemCount == array.length){
            setCapacity(itemCount + 1);
        }
        for (int j = itemCount; j > i; j--){
            array[j] = array[j-1];
        }
        array[i] = new Item(value);
        itemCount++;
    }

O(n) - again- i'm not even too sure one this one

Line number On/Off

Code: Select all

public boolean remove (String value) {
        //search array from index 0 upwards
        int i = 0;
        for (i = 0; i < itemCount; i++){
            Item curItem = (Item)array[i];
            String curValue = curItem.getValue();
            int result = value.compareTo(curValue);
           
            // if theres more than one, decrement
            if (result == 0) {
               curItem.decOccurrences();
           
               // if there is only one, remove item and fill hole
               if (curItem.getOccurrences() == 0){
                   
                    for (int j = i; j<itemCount - 1; j++){
                        array[j] = array [j+1];
                   
                    }
                    itemCount --;   
               }

               return true;
            }   
            else if (result < 0){
                return false;     
            }

        }
        return false;
    }

March 17th, 2005, 7:32 am

You got them all right; it is a little simpler that it seems at first.
The ones you weren't too sure of are right too; as soon as you start looping till you've reached a variable, it's O(n) - I guess that says itself

Good luck with the rest.

March 17th, 2005, 8:22 am

alright! one question though- I was looking at the last one- which has a loop nested in a loop so shouldnt that be O(n^2) ?

March 22nd, 2005, 7:52 am

Well, in the first loop, the limit is itemCount.
In the second one, the limit is (itemCount -1).

They're two different values, although being very close to eachother.
The 'n' in O(n) would represent (itemCount * (itemCount -1)). If you start using a constant, like in O(n^2), you would have to have the same two values: (itemCount *itemCount ). Not necessarily the same variables, but the same values.

Torsten.

March 22nd, 2005, 8:30 pm

susancbk wrote:

The concept of Big O is quite confusing to me, but i've given a go at it, and was wondering if anyone could provide some correction/suggestions/advice.

Well, if you use a variable named n, you must explain what n actually means. Because some of these algorithms don't involve a value known as "n."

Technically, Big-O notation simply represents a set of functions -- the set of functions which grow at a slower or equal pace as the given function. When we say an algorithm runs in O(n^2) time, we mean that the amount of time it takes for the algorithm to run grows at a slower or equal pace as the function f(n) = n^2. "Growing at the same pace" means that as n grows really large, the ratio T(n)/(n^2 (where T(n) is the runtime for an input of size n) will either equal a constant number, like 3, or 20.5, or 0.2. "Growing at a slower pace" means that the ratio will get closer and closer to zero. Maybe this is redundant, but I can't be sure how well this has been explained.

susancbk wrote:

O(1) because it will take a fixed amount of time and dosen't matter what the number of things to do is.

Line number On/Off

Code: Select all

public void add (Object item) {
       if (isFull()){
            addToCapacity(3);
       }
       array[rear] = item;
       rear = (rear + 1) % array.length;
       itemCount++;
    }

This is not the case. You have to be careful. I annotated your function below:

Line number On/Off

Code: Select all

public void add (Object item) {
       if (isFull()){
        // Testing isFull() takes O(1) operations.
            addToCapacity(3); // takes O(n) operations.
       }
       array[rear] = item; // This assignment takes O(1) operations
       rear = (rear + 1) % array.length; // O(1) operations
       itemCount++; // O(1) operations
    }

So most of the operations take O(1) runtime -- they run in a fixed amount of time. If all of them did, then the function would run in O(1) time, since 1+1+1+1+1 is 5, which is just a multiple of 1. But the addToCapacity function doesn't. The addToCapacity function takes O(n) operations. And 1+1+1+1+1+n runtime is O(n).

So the amount of time it takes to run the function, in the worst case, will be O(n).

When you analyse the runtime of an algorithm, you can't just look for for loops, you need to analyse the runtime line-by-line, and combine the parts together. When you have a for loop, figure out how much time the block will take to run, and then ask, "how many times will this block be called?", and multiply.

By the way, instead of adding 3 to the capacity, it is better to double the capacity, unless the capacity is zero, in which case make it equal to 1. If you add 3, you'll have to do a whole number of recopyings of the array. If you double the capacity, you'll have to do less recopying, in case somebody decides to add elements with

Line number On/Off

Code: Select all

for (i = 0; i < 1000; ++i) {
        add(i);
}

Putting objects on the end of an array or vector over and over again is a common practice.

If you add 3 to the length each time, you'll need to recopy a number of elements equal to 3 + 6 + 9 + 12 + ... + 999, which is equal to 166833 copy operations. If you double the length each time, you'd have to only recopy objects 1 + 2 + 4 + 8 + 16 + ... + 512 times, which is equal to 1023.