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

## Are there variations of the regular runtimes of the Big-O-Notation?

There are multiple $$O$$-Notations, like $$O(n)$$ or $$O(n^2)$$ and so on. I was wondering, if there are variations of those in reality such as $$O(2n^2)$$ or $$O(\log n^2)$$, or if those are mathematically incorrect.

Or would it be a right thing to say that it is possible to improve a $$O(5n^2)$$ to a $$O(3n^2)$$? I can’t and don’t need to figure out runtimes yet and I do not need to improve anything, but I’d need to know if this how you describe your functions in reality.