Question 46
What is the time complexity to update a single value in a Fenwick Tree (Binary Indexed Tree) of size N?
A Fenwick Tree updates non-overlapping prefix sums by adding the lowest set bit (i += i & -i) at most log2(N) times.
What is the time complexity to update a single value in a Fenwick Tree (Binary Indexed Tree) of size N?
A Fenwick Tree updates non-overlapping prefix sums by adding the lowest set bit (i += i & -i) at most log2(N) times.
Which strategy does Strassen's Matrix Multiplication algorithm use to reduce multiplication steps from 8 to 7?
Strassen's algorithm divides N x N matrices into 2x2 sub-blocks and recursively computes 7 products instead of 8, reducing time complexity to O($N^2$.807).
In a Threaded Binary Tree, NULL pointers in leaf nodes are replaced with pointers to:
Threaded Binary Trees utilize empty left/right child pointers to store direct links to the in-order predecessor or successor, enabling stackless in-order traversal.
What is the amortized time per operation in a Disjoint Set Union (DSU) using both path compression and union by rank?
Combining path compression with union by rank (or size) gives an amortized O($\alpha(N)) time per operation$, where $\alpha$ is the inverse Ackermann function.
Which collision resolution technique in Hash Tables uses a linked list for each hash bucket?
Separate Chaining handles collisions by storing all elements that hash to the same bucket index in a linked list attached to that bucket.