Tag Info

Accepted

Binary search tree with height of max 1.44 * log(n) is AVL tree or it's not an iff

If a binary search tree on $n$ nodes is an AVL tree, then its height $h$ is at most about $1.44 \log n$. The converse doesn't hold: Take a large complete binary tree, and add a short path (...
• 1,333

Proving $f(n) = 1 + c + c^2 + \cdots + c^n = \Theta(1)$

Since $c^0=1$, you can re-write your function in the following way: $$f(n)=\sum_{i=0}^n c^n \ .$$ That said, in order to prove that $f(n)=\Theta(1)$, you have to show that $f(n)$ is both $\Omega(1)$ ...
• 1,069

The $\Theta(n)$ is the number of hash operations. You can create a horribly bad hash operation, but the number of awfully slow operations would still be $\Theta(n)$.
• 31.1k
1 vote

Find all intervals that are contained in a query interval

This is an old question, but for the sake of posterity, there is a formulation that beats the worst-case $O(n)$ solution proposed by @D.W. with $O(\log n + k)$, where $k$ is the number of returned ...
• 63
1 vote

Are dictionaries and associative arrays the same thing?

Depends on the language. On the abstract level of this computer science concept, they are fundamentally synonyms. They are the same thing. One of those concepts where multiple people came up with ...

Only top scored, non community-wiki answers of a minimum length are eligible