Time complexity of NP Complete reduction - polynomial time NP Complete problems (typically exponential complexity) - Traveling Salesmen problem, Knapsack problem, Hamiltonian path problem
Time Complexity:
Linked list operations - order N
Balanced BST - order log(N)
Worst case BST - order N
Heap insert/remove - order log(N)
Queue push/pop w/o tail - order N
Queue push/pop w/ tail - constant time
Stack push/pop - constant time
Inserting to heap:
Insert at next position
Upheap
Removing from heap:
Replace root with last inserted
Downheap