All Questions
4 questions
7
votes
7
answers
6k
views
Is there a meaningful difference between O(1) and O(log n)?
A computer can only process numbers smaller than say $2^{64}$ in a single operation, so even an $O(1)$ algorithm only takes constant time if $n<2^{64}$. If I somehow had an array of $2^{1000}$ ...
- 171
10
votes
2
answers
19k
views
Memory complexity?
I am unclear about finding the memory complexity of an algorithm.
Some places refer memory complexity as what container would be carrying for instance:
...
- 381
6
votes
1
answer
6k
views
Is every algorithm's complexity $\Omega(1)$ and $O(\infty)$?
From what I've read, Big O is the absolute worst ever amount of complexity an algorithm will be given an input. On the side, Big Omega is the best possible efficiency, i.e. lowest complexity.
Can it ...
- 2,977
0
votes
0
answers
125
views
Worst case lower bound of the general number guessing problem
I have the following problem:
Let Alice and Bob be two people playing games.
Alice and only Alice owns a special device, Robo, that is capable of generating one truly random number $k \in \mathbb{N}$ ...
