All Questions
Tagged with complexity-theory asymptotics
9 questions
26
votes
7
answers
6k
views
Justification for neglecting constant factors in Big O
Many a times if the complexities are having constants such as 3n, we neglect this constant and say O(n) and not O(3n). I am unable to understand how can we neglect such three fold change? Some thing ...
- 1,809
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
5
votes
1
answer
123
views
Exact meaning of $2^{\mathcal{O}(f(n))}$
In Sipser's Introduction to the Theory of Computation he uses the notation $2^{\mathcal{O}(f(n))}$ to denote some asymptotic running time.
For example he says that the running time of a single-tape ...
- 163
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
3
votes
1
answer
1k
views
Big-O / $\tilde{O}$ -notation with multiple variables when function is decreasing in one of its arguments
Say we have an algorithm that
takes an input a triple
($X$, $A$, $\epsilon$),
where $X$ is a sequence of $n$ bytes, of which the algorithm might query only a subset, and $A$ and $\epsilon$ are ...
- 51
1
vote
1
answer
129
views
Asymptotic notation for summations
I am struggling to understand why this property of asymptotic notation is true
- 123
1
vote
1
answer
464
views
General Number Field Sieve Big O Clarification
This paper states that the general number field sieve is of order:
$$L\approx\exp\left((64/9)^{1/3}\,n^{1/3}\,(\ln(n))^{2/3}\right)$$
However several sources (e.g. Wolfram) give it as:
$$O\left( \...
- 115
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}$ ...
