0

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())
    {
        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?

Improve this question

4 Answers 4

Reset to default
5

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

From an academic p.o.v. and big-Oh notation p.o.v. this is 100% correct. I thought it would be interesting to note though that for comparing two O(n) algorithms the number of atomic operations per N is also interesting (for atomic in this context think of (floating) point operations, logical operations and branching)
3

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.

Improve this answer

Comments

0

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))!

Improve this answer

Comments

0

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(n2). In between, it may be O(n log n).

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.