# 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$$?