1/123
Looks like no tags are added yet.
Notation: n = number of elements/nodes
O(1) = Constant time
Notation: O(log n)
Logarithmic time
Notation: O(n)
Linear time
Notation: O(n log n)
Linearithmic time
Notation: h
Height of the tree
Circular Queue (CLL) - Enqueue
O(1)
Circular Queue (CLL) - Dequeue
O(1)
Circular Queue (CLL) - Peek / Front
O(1)
Circular Queue (CLL) - Rear element
O(1)
Circular Queue (CLL) - IsEmpty
O(1)
Circular Queue (CLL) - Search
O(n)
Circular Queue (CLL) - Traversal / Display
O(n)
Circular Queue (CLL) - Count elements
O(n)
Circular Queue (CLL) - Space complexity
O(n)
Why is enqueue O(1) in Circular Queue CLL?
Only pointers are updated; no traversal is needed.
Why is dequeue O(1) in Circular Queue CLL?
Only pointers are updated; no traversal is needed.
DLL - Insertion at beginning
O(1)
DLL - Insertion at end with tail pointer
O(1)
DLL - Insertion at specific position
O(n)
DLL - Deletion at beginning
O(1)
DLL - Deletion at end with tail pointer
O(1)
DLL - Deletion at specific position
O(n)
DLL - Searching
O(n)
DLL - Forward traversal
O(n)
DLL - Backward traversal
O(n)
DLL - Accessing element by position
O(n)
DLL - Updating element by position
O(n)
DLL - Space complexity
O(n)
Why is DLL insertion at beginning O(1)?
Only a fixed number of pointers are updated.
Why is DLL deletion at beginning O(1)?
Only a fixed number of pointers are updated.
When is DLL insertion at end O(1)?
When a tail pointer is maintained.
When is DLL deletion at end O(1)?
When a tail pointer is maintained.
Why is DLL insertion at a specific position O(n)?
The position must first be located by traversal.
Why is DLL deletion at a specific position O(n)?
The position must first be located by traversal.
Circular Array Deque - Insert at front
O(1)
Circular Array Deque - Insert at rear
O(1)
Circular Array Deque - Delete from front
O(1)
Circular Array Deque - Delete from rear
O(1)
Circular Array Deque - Get front element
O(1)
Circular Array Deque - Get rear element
O(1)
Circular Array Deque - Search
O(n)
Circular Array Deque - Traversal / Display
O(n)
Circular Array Deque - Access by index
O(1)
Circular Array Deque - Space complexity
O(n)
DLL Deque - Insert at front
O(1)
DLL Deque - Insert at rear
O(1)
DLL Deque - Delete from front
O(1)
DLL Deque - Delete from rear
O(1)
DLL Deque - Get front element
O(1)
DLL Deque - Get rear element
O(1)
DLL Deque - Search
O(n)
DLL Deque - Traversal / Display
O(n)
DLL Deque - Access by position
O(n)
DLL Deque - Space complexity
O(n)
Circular Array Deque vs DLL Deque - Access by index
Circular Array: O(1); DLL: O(n).
Why is insertion at both ends O(1) in a DLL Deque?
Both front and rear pointers are directly available.
Binary Tree - Insertion (general tree)
O(n)
Binary Tree - Deletion (general tree)
O(n)
Binary Tree - Searching
O(n)
Binary Tree - Inorder traversal
O(n)
Binary Tree - Preorder traversal
O(n)
Binary Tree - Postorder traversal
O(n)
Binary Tree - Level order traversal
O(n)
Binary Tree - Finding height
O(n)
Binary Tree - Finding maximum element
O(n)
Binary Tree - Finding minimum element
O(n)
Binary Tree - Counting total nodes
O(n)
Binary Tree - Counting leaf nodes
O(n)
Binary Tree - Space complexity
O(n)
Why is binary tree traversal O(n)?
Every node is visited exactly once.
Does a general binary tree guarantee O(log n) searching?
No. Searching can require visiting every node.
BST - Insertion (best / average case)
O(log n)
BST - Insertion (worst case)
O(n)
BST - Deletion (best / average case)
O(log n)
BST - Deletion (worst case)
O(n)
BST - Searching (best / average case)
O(log n)
BST - Searching (worst case)
O(n)
BST - Finding minimum (best / average case)
O(log n)
BST - Finding minimum (worst case)
O(n)
BST - Finding maximum (best / average case)
O(log n)
BST - Finding maximum (worst case)
O(n)
BST - Finding inorder successor (best / average case)
O(log n)
BST - Finding inorder successor (worst case)
O(n)
BST - Finding inorder predecessor (best / average case)
O(log n)
BST - Finding inorder predecessor (worst case)
O(n)
BST - Inorder traversal
O(n)
BST - Preorder traversal
O(n)
BST - Postorder traversal
O(n)
BST - Finding height
O(n)
BST - Space complexity
O(n)
Why are BST search operations O(log n) on average?
The tree is reasonably balanced and its height is approximately log n.
Why are BST operations O(n) in the worst case?
The BST becomes skewed, behaving like a linked list.
What is the height of a balanced BST approximately?
O(log n)
What is the height of a skewed BST approximately?
O(n)
AVL - Insertion
O(log n)
AVL - Deletion
O(log n)
AVL - Searching
O(log n)
AVL - Finding minimum
O(log n)
AVL - Finding maximum
O(log n)
AVL - Finding height recursively from scratch
O(n)