CODEWITHSUNDEEP
linked-listbig-o
Mr.Rabbit
Mr.Rabbit

Reputation: 101

Big-O for while loop?

How do I solve the Big-O for this problem containing a while loop that goes through the nodes and increment the length as long as it does not equal to null? Would this just be O(N) because it goes through N nodes? Also, the statements within the while loop would just be O(1), correct? 

/**
*@param head the first node of the linked list 
*@return the length of the linked list
*/
public static <E> int getLength(Node<E> head) {
    int length = 0; 
    Node<E> node = head;
    while (node!=null) {
        length++;
        node = node.next; 
    }
    return length;
}

Upvotes: 1

Views: 389

Answers (1)

mihovale
mihovale

Reputation: 66

As you said the traversal of a linked list takes O(N) since you need to go over each node once.

The assignment operator is O(1), since you need to do this just once, every time.

Upvotes: 3

Related Questions