Quiz: Time and Space Tradeoffs

A binary lifting table for $n$ nodes uses $O(n \log n)$ space and answers queries in $O(\log n)$. If you stored every ancestor directly, what would the space and query time be?

1. A.$O(n)$ space, $O(n)$ query time
2. B.$O(n^2)$ space, $O(1)$ query time
3. C.$O(n \log n)$ space, $O(1)$ query time
4. D.$O(n)$ space, $O(1)$ query time