CODEWITHSUNDEEP
arraylistlinked-listruntimebig-oindexof
davedno
davedno

Reputation: 349

Big O runtime - indexOf LinkedList/ ArrayList

I have a question considering Big O runtime and the indexOf method within LinkedList, and ArrayList. How can I come up with a Big O runtime assumption and how would it be different in a Linked List as opposed to an Array List?

LinkedList indexOf()

public int indexOf(Object value)
{
    int results = -1;
    boolean done = false;
    Node<E> ref = head.next;
    for(int i = 0; i < size && !done; i++)
    {
        if(value.equals(ref.value))
        {
            results = i;
            done = true;
        }
        ref = ref.next;
    }
    return results;
}

ArrayList indexOf()

if (o == null) {
            for (int i = 0; i < size; i++)
                if (Values[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(Values[i]))
                    return i;
        }
        return -1;

I apologize if this is a trivial question to some but I am going to need to understand how to come up with a Big O runtime of a method.

Upvotes: 2

Views: 2104

Answers (1)

Mureinik
Mureinik

Reputation: 312008

In both these implementations you have nothing better to do than go over the list one element at a time and compare it to the value you're looking for. At the worst case, you'd be going through the entire list, giving a complexity of O(n).

Upvotes: 2

Related Questions