Queue<T> O(1)time

Question

I just created the enqueue, dequeue and peek methods, but i don't know whether they are in O(1) time. if it is not, how can i do, and Can you explain how to do it in O(1) time?

Node<T> start;

public void enqueue(T val) 
{
    Node<T> n = new Node<T>(val);

    if (start == null) 
    {
        start = n;
    } else 
    {
        n.next = start;
        start = n;
    }       
}   
public T dequeue() 
{
    if (start != null) 
    {
        T item = start.nodeValue;
        start = start.next;

        return item;
    }
    return null;
}


public void peek () 
{
    Node<T> curr = start;
    while (curr != null) 
    {
        System.out.print(curr.nodeValue + " ");
        curr = curr.next;
    }
}

Answer 1

Well, enqueue and dequeue run in constant time, and peek runs in linear time.

The idea for analysing complexity is merely counting the number of operations. All we have to do is assume that creating a node, assigning a value and evaluating an if statement run in O(1).

For enqueue and dequeue, no matter where the code runs, there is a constant number of those operations. So in the end, the code just does a constant number of O(1) operations, which gives O(1) complexity.

For the peek method, the code enters the wile as many times as there are nodes in the queue. So if there are n nodes, the code enters n times the loop: it does n O(1) operations. In the end: peek has linear complexity.

Having a method print all the values of the queue running linear time is really no big deal, as it involves iterating through the structure.

Answer 2

They are in O(1), or constant time, because the time it takes for the operations is not affected by the collection size.