I wrote code for an enqueue method in a singly linked list and I'm wondering if anyone can tell me the Big O is for this code. I at first assumed it was O(n) because of the loop. However, the loop will always iterate a specific number of times depending on how many items are in the list. This makes me believe it's actually O(1). Am I wrong?

public Node<T> enqueue(T data){
        Node<T> toQueue = new Node<>(data);
        if (this.head == null) {
            this.head = toQueue;
            return toQueue;
        }
        Node<T> lastNode = this.head;
        while(lastNode.next != null){
            lastNode = lastNode.next;
        }

        lastNode.next = toQueue;

        return toQueue;
    }

CodePudding user response：

Let's start from the following excerpt from the question:

However, the loop will always iterate a specific number of times depending on how many items are in the list.

This is a correct statement.

Please, note the dependency on the input size:

iterate a specific number of times depending on how many items are in the list

Therefore, the algorithm has the linear time complexity — O(n).

Linear time complexity

A slightly reformatted excerpt from the article: Time complexity: Linear_time - Wikipedia:

An algorithm is said to take linear time, or O(n) time, if its time complexity is O(n). Informally, this means that the running time increases at most linearly with the size of the input. More precisely, this means that there is a constant c such that the running time is at most cn for every input of size n. For example, a procedure that adds up all elements of a list requires time proportional to the length of the list, if the adding time is constant, or, at least, bounded by a constant.

A slightly reformatted excerpt from the article: Big O notation: Orders of common functions - Wikipedia: let's refer to the corresponding row:

Notation: O(n)

Name: linear

Example: Finding an item in an unsorted list or in an unsorted array; adding two n-bit integers by ripple carry

CodePudding user response：

However, the loop will always iterate a specific number of times depending on how many items are in the list. This makes me believe it's actually O(1).

Am I wrong?

Your reasoning is wrong.

A complexity analysis of an algorithm needs to take account of all possible inputs.

While the number of elements in a single given list can be assumed to be constant while you are looping, the number of elements in any list is not a constant. If you consider all possible lists that could be inputs to the algorithm, the length of the list is a variable whose value can get arbitrarily large¹.

If we call that variable N then it is clear that the complexity class for your algorithm is O(N). (I won't go into the details because I think you already understand them.)

The only way that your reasoning could be semi-correct would be if you could categorically state that the input list length was less than some constant L. The complexity class then collapses to O(1). However even this reasoning is dubious², since the algorithm as written does not check that constraint. It has no control over the list length!

On the other hand, if you rewrote the algorithm as this:

public static final int L = 42;

public Node<T> enqueue(T data){
    Node<T> toQueue = new Node<>(data);
    if (this.head == null) {
        this.head = toQueue;
        return toQueue;
    }
    Node<T> lastNode = this.head;
    int count = 0;
    while(lastNode.next != null){
        lastNode = lastNode.next;
        if (count   > L) {
           throw InvalidArgumentException("list too long");
        }
    }

    lastNode.next = toQueue;

    return toQueue;
}

then we can legitimately say that the method is O(1). It will either give a result or throw an exception within a constant time.

^{1 - I am ignoring the fact that there are practical limits on how long a simple linked list like this can be in a Java program. If the list is too large, it won't fit in the heap. And there are limits on how large you could make the heap.
2 - A more mathematically sound way to describe the scenario is that your algorithm is O(N) but your use of the algorithm is O(1) because the calling code (not shown) enforces a bound on the list length.}