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

# Tag: runtimes

## 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.