analysing an algorithm for time complexity

I have written a function that merges two linked list. (Note that the function is based on pre-given code in case you wonder why i'm calling a function node(i)).

public SLL mergeUnsorted(SLL otherList)
{
    // find length of this list
    int length = 0 ;
    Iterator itr = this.iterator() ;
    while (itr.hasNext())
   开发者_JAVA百科 {
        Object elem  = itr.next() ;
        length++ ;
    }

    // get each node from this list and
    // add it to front of otherList list
    int i = length -1 ;
    while (i >= 0)
    {
        // returns node from this list
        SLLNode ins = node(i) ;

        ins.succ = otherList.first ;
        otherList.first = ins ;
        i-- ;
    }
    return this ;
}

first part O(n) second part O(n)

overall complexity O(n)

or is it O(n^2) because i traverse the list twice?

Traversing twice is just a constant multiplier. As long as the multiplier doesn't depend on n, it's still O(n). EDIT: However, do make sure that inserting into the other list is constant-time. If the time to do it is proportional to the size of the other list, well, I think you can see what happens then.

Because you traversed the list twice, it's O(2n).. which is O(n). It is linear growth.

Also, in most programming languages, the length of a collection is already tracked, so you can just pull that property instead of iterating twice.

An example of an O(n^2) algorithm would be something like finding the intersection of elements in two arrays. It is O(n^2) because you'd take the first element from the first array and compare it to every element in the second array. Then you take the second element and compare it to every element in the 2nd array. repeat.

As food for thought, you can turn the above example into O(n) by hashing all the elements in one array (which is O(n)) and then check each element in the 2nd array (also O(n))!

A simple way to find out for yourself is to run the code with different values of n. Try for instance 10, 100, 1000, 10000, ... until you get non-trivial times. When you multiply n by 10, what happens to the time? If n * 10 => time * 10, it's O(n). If n * 10 => time * 100, it's O(n²). In between, it may be O(n log n).