Answer to Question #149034 in Java | JSP | JSF for Serk

Question

Critically evaluate the complexity of an. Implemented ADT/ algorithms

Answer 1

There are many types of ADT. Few of them with their time complexity are:

1.Linked List:

Insertion:O(1), if it is done on the head otherwise in all other cases O(n), because to reach that position it has to traverse n elements.

Deletion:same as insertion.

Searching: O(n).

2.Stack:

Push: O(1)

Pop: O(1)

Top: O(1)

Because it inserts from bottom and deletes from top (LIFO), while inserting the pointer is at top and while deleting it is at the end. So it has to traverse only 1 element. Hence, O(1) in all the cases.

3. Queue

Insert: O(1)

Remove: O(1)

Size: O(1)

It follows FIFO approach. So, It has to traverse only 1 element both the times. Hence, O(1).