Compressed Trie Run-time(s)


Consider a set $ X$ $ =$ $ \{x_1, x_2, …, x_n\}$ where every $ x_i$ is a positive integer and $ x_i \leq n^f$ for some constant $ f$ . We represent $ x_i$ as strings over an alphabet $ 0, 1, …, 2^t – 1$ (in other words, representing each $ x_i$ in base $ 2^t$ ) and store all $ x_i$ from $ X$ in a compressed trie $ T$ . For every node $ u$ of $ T$ we keep an array $ A(u)$ of size $ 2^t + 1$ . $ A(u)[i]$ contains a pointer to the child $ u_i$ of $ u$ such that the edge from $ u$ to $ u_i$ is marked with $ i$ ; $ A(u)[i] = NULL$ if there is no such $ u_i$ in $ T$ . Specify all of the following in big-$ O$ in terms of $ f$ , $ n$ , and $ t$ (as necessary). What is the maximum height of $ T$ ? What is the total space usage of $ T$ and all $ A(u)$ ? What time is needed to search for a key $ k$ in $ T$ ?