give the worst case complexity for the following operations if the data structur

Question

give the worst case complexity for the following operations if the data structure has n elements(using big O notation)

append a node to a linked list with has only a head pointer ---> answer: O(n), but why is it that

prepend a node to a liked list with ony a head pointer ----> answer: O(1), but why is is that

binary search of a sorted array ---> answer : O(logn), but why is that

adding a node to the proper locarion in a balanced binary search tree---> answer: O(logn), but why is that

printing all node in order in a binary tree ---> answer: o(n), but why is that

adding a node in an imbalanced binary search tree--->answer : o(n), but why is that

Explanation / Answer

append a node to a linked list with has only a head pointer ---> answer: O(n)

The reason is , since we have the address of the head pointer only ,inorder to insert a node at the end of the list we need to find the last node. To find the last node we have to check whether each node is last or not by checking the next pointer. If next pointer is NULL then it is the last node.

As we have n items in the list, we need to check n nodes that takes O(n)

2. prepend a node to a liked list with ony a head pointer ----> answer: O(1)

The reason is,Here what ever the size of the linked list we do not need to find last node .

simply we create a new node and prepend to head node whose address is already available , so no loops required it is O(1).

3.binary search of a sorted array ---> answer : O(logn)

Here in each iteration the size of the array is decremented to half,

In first iteration array size is n, second iteration n/2, in third iteration it is n/4, in fourth n/8 and so on.

Therefor it is O(log n).

4.adding a node to the proper locarion in a balanced binary search tree---> answer: O(logn)

In a balanced binary search tree in every iteration we select the subtree with half of its size, so it is O(log n);

5.printing all node in order in a binary tree ---> answer: o(n),

To print all the nodes we need to traverse all the nodes , as there are n nodes , to traverse all the n nodes we need O(n).

6.adding a node in an imbalanced binary search tree--->answer : o(n),

In unbalanced tree the size of the sub tree maximum size is n assuming no elements in one subtree, so it is in worst case O(n).

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.