Skip to main content
6 votes
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 (...
Ashwin Ganesan's user avatar
4 votes

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)$ ...
SilvioM's user avatar
  • 1,069
2 votes

How bad re-hashing can cost?

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)$.
gnasher729's user avatar
  • 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 ...
Jordan's user avatar
  • 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 ...
Richard Balkins's user avatar

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