All Questions
Tagged with complexity-theory asymptotics
145 questions
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
1
vote
1
answer
144
views
What exactly is bigO notation? [duplicate]
I've heard of bigO notation but I don't really understand how do I determine it for my code and what exactly does it represent?
I heard that there are two:
RunTime
Memory Complexity
How can I learn ...
- 113
0
votes
1
answer
250
views
Relation between best case and average case complexity
I have two questions,
Does $T_\mathrm{best}(N) = O(f(N))$ imply that $T_\mathrm{avg}(N) = \Omega(f(N))$?
Does $T_\mathrm{avg}(N) = O(f(N))$ imply that $T_\mathrm{best}(N) = O(f(N))$?
Where,
\begin{...
2
votes
1
answer
2k
views
Can we count the number of inversions in time $\mathcal{O}(n)$?
It is possible to find the total number of inversions by $\mathcal{O}(n\log{}n)$ running time (extension of merge-sort algorithm for example).
Is there more asymptotically efficient way to do it? $\...
- 215
2
votes
1
answer
160
views
Why is big omega of peak finding Omega(lg n)?
Why is big omega of finding a peak in an unsorted array Omega(lg n), not Omega(1)?
I understand that peak finding is O(lg n), because in the worst case, we find a peak in the last possible step, so ...
- 21
0
votes
3
answers
182
views
Complexity calculation of a recursive function with additional O(n) complexity
There is a method that I want to calculate its complexity in asymptotic notation. It calls additional methods(equals and substring) which complexity is $O(n)$. If it was $O(1)$, I could figure out ...
2
votes
2
answers
530
views
How can I compare two recurrence relation to find which one is better on large inputs
I have two recurrences:
$T_1(n) = 2 T_1(n-1) + n$ if $n > 1$, $1$ if $n = 1$
$T_2(n) = 2 T_2(\frac{n}{2}) + n^2$ if $n > 1$, $2$ if $n = 1$
Does this mean $T_1$ is better than $T_2$ because ...
- 23
-1
votes
2
answers
494
views
Solve using master method $T(n) = n · T(n/2) + n^{\log n}$ [closed]
$T(n)=n\displaystyle \cdot T\left(\frac{n}{2}\right)+n^{\log_{2}n}$.
$f(n) = n^{\log_{2}n}$
Number of leaves = $n^{\log_{a}b} = n^{\log_{2}n}$
CASE 2 (All level same)
$f(n) = \Theta(n^{\log_{b}a} {...
- 135
3
votes
2
answers
2k
views
Time complexity of functions that call each other
I'm having trouble reasoning about the time complexity of these mutually recursive functions. This was asked on SO here but the answer there didn't help me. I tried substituting one of the recurrences ...
- 133
13
votes
1
answer
2k
views
Algorithms with O(sqrt(N)) SPACE complexity?
Are there any known algorithms for formulated problems that require a SPACE complexity of O(sqrt(N))? I know that algorithms with that big-O time complexity exist.
- 131
1
vote
1
answer
42
views
Is the potential difference in the two consecutive states of a data structure equal to the credit of the change inducing operation?
I am following CLRS for studying Amortized analysis with potential function and there I came through the following :
Let a data structure go through states : $D_0 $ $D_1$ $D_2$ $ ....$ $D_n$ while ...
- 173
0
votes
1
answer
149
views
Complexity class for concurrent algorithms
We have the big O notations for sequential algorithms , but is there a notation to represent parallel algorithms in a similar way?
Motivation:
A sequential algorithm may be O(n7) but its parallel ...
- 109
2
votes
3
answers
308
views
Asymptotic equivalent of the recurrence T(n)=3⋅T(n/2)+n
The questions is to find the running time $T(n)$ of the following function:
$$T(n)=3\cdot T(n/2) + n \tag{1}$$
I know how to solve it using Master theorem for Divide and Conquer but I am trying to ...
1
vote
1
answer
67
views
How do I find running time for the following divide and conquer problem?
Question is to find the runtime $T(n)$ of following problem by solving the recurrence.
$T(n)=16\cdot T(\frac{n}{4}) + n!$.
I went through the following theory.
If the recurrence relation is of the ...
4
votes
3
answers
452
views
Is $\Omega(\sqrt{n}!)=\Omega(2^{\sqrt{n}})$ correct?
I'm very confused when I see the following statement in the famous CLRS book "Introduction to Algorithms (3rd)", ch34.2, page 1063:
...and therefore the running time is $\Omega(m!)=\Omega(\sqrt{n}!)...
- 39
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
4
votes
1
answer
3k
views
Complexity of division
The article Computational complexity of mathematical operations mentions that the complexity of division in $O(M(n))$, and that "$M(n)$ below stands in for the complexity of the chosen multiplication ...
- 270
1
vote
4
answers
623
views
Complexity analysis of an unsolvable algorithmic problem?
In my automata theory class, for our term project we are required to present a complexity analysis for our algorithmic problem. I have chosen an unsolvable problem, and he has off-the-cuff mentioned ...
- 51
3
votes
2
answers
898
views
how to prove that nlogn is not Θ(n) without using limits?
i'm studying an algorithms designing and analysis , and i've question about Big-theta
how can i prove that nlogn is not Θ(n) without using limits ?
- 31
7
votes
2
answers
2k
views
Confusion with analysis of hashing with chaining
I was attending a class on analysis of hash tables implemented using chaining, and the professor said that:
In a hash table in which collisions are resolved by
chaining, an search (successful or ...
- 275
1
vote
1
answer
346
views
What set of primitive operations are assumed to be constant time in complexity analyses?
Different set of primitive operations lead to different complexity of certain problems. For example, sorting by comparison is only O(N*log(N)) if one assumes both ...
- 4,159
3
votes
1
answer
75
views
How do I find an upper bound on this recurrence
$f(n)=f(n-\sqrt{n})$
I believe $f(n)\in O(\sqrt{n})$
However I cannot seem to prove it, my intuition comes from the fact that we can remove $\sqrt{n}$ exactly $\sqrt{n}$ times, but if $n$ shrinks ...
- 195
0
votes
1
answer
364
views
Binary tree algorithm asymptotic analysis problem
Assume we have a perfectly balanced Binary tree.
We have the following algorithm: For each passed node, traverse through all its ancestors and then do the same algorithm for the left and right child ...
- 103
3
votes
1
answer
68
views
How to state that a complexity bound does not depend on a given parameter size?
I am often ill at ease with Landau (Big O) notation, because it seems
often to be abusing mathematical notation. The best example is the use
of the equal sign to express a set membership. And this can ...
- 19.6k
3
votes
1
answer
102
views
Are there algorithms with non-convex and non-concave computational complexity?
If I am not mistaken, an algorithm that runs in time $\Theta(f(n))$ also runs in $\Theta(f(n) + a\sin(bn))$ where $a,b$ are conveniently chosen constants. Therefore I believe that the computational ...
- 383
1
vote
2
answers
340
views
Complexity of nested loops [duplicate]
I'm trying to figure out the complexity of the following algorithm.
...
- 73
0
votes
2
answers
102
views
How can random array access be considered $O(1)$ if bits must be stored in space and light travels at finite speed?
Bits are usually stored linearly in space. We can say, thus, that the length of a memory chip, for example, is linearly proportional to the number of bits it can hold. Since signals must travel at ...
- 73
3
votes
1
answer
4k
views
Time complexity of Dynamic Array via repeated doubling
When we implement dynamic array via repeated doubling (if the current array is full) we simply create a new array that is double the current array size and copy the previous elements and then add the ...
- 133
0
votes
2
answers
12k
views
Using induction to prove a big O notation [duplicate]
I'm trying to prove that the following recurrence relation has a runtime of O(n):
fac(0) = 1
fac(n+1) = (n + 1) * fac(n)
...
- 111
0
votes
3
answers
443
views
Big O relation between $2^n$ and $2^{2n}$
I know that:
If $f(n) = O(g(n))$ , then there are constants $M$ and $x_0$ , such that
$f(n) <= M*g(n), \forall n > n_0$
The other, plain English way of defining it is,
If $f(n)=O(g(n))$ ...
- 399
0
votes
1
answer
39
views
How to analyse the complexity of a problem with two or more size measures
Consider this example: a problem of dimension $n$ and $m$ ($m,n$: any given integers).
has a search space of size $O(n^n * m^n)$.
It is clear that this problem is exponential in $n$,
whatsoever $m$ ...
- 101
1
vote
1
answer
763
views
Blum's speedup theorem in big-O format?
Is there a way to state Blum's speedup theorem in terms of Big-O (Landau) notation?
- 11.1k
8
votes
2
answers
171
views
Is there always a Big Oh complexity strictly between any two others?
I'm learning about asymptotic analysis, and have seen some exotic looking complexities living between other common ones. For instance "log log n" is strictly between 1 and log n. It makes me wonder if ...
- 183
-2
votes
1
answer
75
views
Big O Notation - Find a Function That Represents the Statement
There's an f(n) such that f(n) != O(f(n/2))
so by the definition of big O notation:
for ...
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
5
votes
1
answer
4k
views
Trouble understanding how to pick constants to prove big theta
So I'm reading Introductions to Algorithms and sometimes I wish it would be a little bit more friendly with how it explains topics. One of these topics is proving big-theta.
I understand that the ...
- 145
2
votes
2
answers
1k
views
A Problem on Time Complexity of Algorithms
For every integer $t$, is there a problem whose solutions can be verified in $O(n^{s})$ time but cannot be found in $O(n^{st})$ time?
By verifying, I mean that given a candidate solution $y$, we can ...
- 21
5
votes
1
answer
2k
views
Algorithms with polynomial time complexity of higher order
I was learning about algorithms with polynomial time complexity. I found the following algorithms interesting.
Linear Search - with time complexity $O(n)$
Matrix Addition - with time complexity $O(n^...
- 296
0
votes
1
answer
63
views
Show that a function belongs to grade of incline [duplicate]
This is a Data structures & Algorithms question. For instance I have the following grades of functions: $O(1), O(2^n), O(n \log n), O(e^n), O(n^3), O(n^{1/3})$ and $O(\log \log n)$
I need to ...
user1125177
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
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
2
votes
1
answer
865
views
Why does every member $f(n) \in \Theta(g(n))$, and $g(n)$ have to be asymptotically non-negative?
The following is an excerpt from CLRS:
The definition of $\Theta (g(n))$ requires that every member $f(n) \in \Theta(g(n))$ be asymptotically nonnegative, that is, that $f(n)$ be nonnegative whenever ...
- 364
7
votes
2
answers
211
views
Two functions $g(n)$, $G(n)$ such that $g(n) = o(G(n))$ but $g(n+1) \neq o(G(n))$
The title of the question expresses what I'm looking for - this is to help me better understand the prerequisites for the Non-Deterministic Time Hierarchy Theorem
For instance, the Arora-Barak book ...
- 592
0
votes
3
answers
2k
views
What is the average search complexity of perfect hashing?
The lookup time in perfect hash-tables is $O(1)$ in the worst case. Does that simply mean that the average should be $\leq O(1)$?
- 41
16
votes
1
answer
404
views
Are asymptotic lower bounds relevant to cryptography?
An asymptotic lower bound such as exponential-hardness is generally thought to imply that a problem is "inherently difficult". Encryption that is "inherently difficult" to break is thought to be ...
- 585