Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [asymptotics]

The tag has no usage guidance.

-3
votes
0answers
52 views

How can we solve the recurrence $T(n) = T(n/2) + log^2(n)$ [on hold]

I am trying to solve the following recurrence: $T(n) = T(n/2) + log^2(n)$ So far I have come up with the following expression $T(n) = \sum^{log(n)}_0 2^klog(n/2^k)$ I cannot figure out a way to ...
-2
votes
1answer
58 views

Which one of the following is the correct asymptotic notation? [closed]

While studying the complexity theory, I encountered a question which is as follows:- Which one of the following is correct? 1) θ(g(n)) = O(g(n)) ∩ Ω(g(n)) 2) θ(g(n)) = O(g(n)) ∪ Ω(g(n)) I know ...
1
vote
0answers
95 views

Growth of random square lattice trees

Consider the problem of growing a random tree on a $L\times L$ square lattice of initially disconnected vertices, starting from an isolated vertex on one of the corners of the lattice and proceeding ...
5
votes
1answer
129 views

What does “hold uniformly” mean in the context of asymptotic analysis?

What does "hold uniformly" mean in the statement of Theorem 1.7 in A Faster Subquadratic Algorithm for Finding Outlier Correlations? Here's the theorem text ("hold uniformly" is in the last line):
2
votes
1answer
75 views

Computing 'Robustness of Magic' of $n$-bit W states

Question What is the asymptotic robustness-of-magic of a $W$ state over $n$ qubits. Is it $\Theta(n)$? $\Omega(\sqrt{n})$? $O\left(\frac{n}{\lg n} \right)$? Background $W$ states are entangled ...
2
votes
1answer
86 views

Reasonable estimate of an asymptotic limit notion of Kolmogorov complexity

Let $$f(c)=\min_{x \ge c} K(x)$$ where $K(x)$ is the kolmogorov complexity of $x$. Since $K(x)$ is always a natural number, there will always be a minimum. My question is, what is the growth rate of $...
0
votes
1answer
181 views

obvious property of big O, big Omega, and big Theta [closed]

I'm trying to determine under what conditions the following statement is true. The statement is, suppose $f(n) = O[g(n)]$ and $f(n) \neq \Theta[g(n)]$ then $g(n) = \Omega[f(n)]$ where $O$ means "...
12
votes
0answers
159 views

What is the curve of “search vs. insert”

Consider a collection of numbers (of arbitrary size), and an oracle that is able to accept two such numbers $a,b$ and answer queries of the form $a<b, a>b, a=b$ in constant time. With this ...
0
votes
1answer
62 views

How can I find tight asymptotic bounds for this half-history recurrence relation?

The recurrence relation $\forall n\in\mathbb{N}\cup\{0\}$ is $T(n)=\Theta(n^2)+2\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}{T(i)}$, with base case of $T(0)=0$. Fairly simple tree analysis shows that $T(n)\...
2
votes
0answers
315 views

the confusion about 'with high probability (w.h.p.)'

w.h.p. can often be seen in the analysis of randomized algorithms. It's definition can be seen here https://en.wikipedia.org/wiki/With_high_probability. However my confusion is that: Assuming we ...
2
votes
1answer
143 views

Preferable way to express $O(n2^n)$

Is it preferable to write $O(n2^n)$ or $O((2 + \epsilon)^n)$? If neither, what is the best way? Since I see a lot of papers with $O(1.42^n)$ instead of $O(2^{\frac{n}{2}})$ and similar transformations,...
-1
votes
1answer
125 views

Using master theorem when there is a constant in the recursive term [closed]

Is it possible to use the master theorem to find the asymptotic growth of a function of the form: $$T(n) = aT(\frac{n}{b}+c)+f(n)$$ Where $c$ is a constant. Can we safely ignore this constant and use ...
2
votes
0answers
235 views

Sieve Methods for Twin Primes - How to extract algorithm from formula

I am reading Cojocaru and Murty's Introduction to Sieve Methods and their Applications. They wait until Chapter 5 to discuss the Sieve of Eratosthenes for finding primes - and their version of it is ...
4
votes
1answer
65 views

Complexity of generically inverting a class of near linear monotonic functions

Given a monotonic increasing function $f(\mathbb{N}) \rightarrow \mathbb{N}$ and a slack function $a(\mathbb{N})\rightarrow \mathbb{N}$, where $f(n) = n \pm O(a(n))$; how many calls to $f$ do we ...
12
votes
1answer
115 views

Decidable theory of asymptotic growth

What are the known limits of the decidability of the comparison of growth rate of functions from $\mathbb{N} \to \mathbb{N}$? I am here thinking of the decidability of questions like "Is $x^x \sim 2^{\...
3
votes
0answers
78 views

What is the state-of-the-art asymptotics for convex optimization?

I've got a convex program of the form: Choose $v \in \mathbb{R}^n$ to minimize $vAv^T$ subject to $O(n)$ linear contraints (including $v \ge 0$). $A$ is a square binary matrix. What algorithm gives ...
1
vote
0answers
205 views

Big-Theta extension of Brent's Theorem?

Is there an extension or translation of Brent's theorem into asymptotics aside from big-$O$? Brent's Theorem: source Running time of a parallel algorithm with $p$ processors (say, $f(n,p)$), $W(n)$ ...
9
votes
1answer
619 views

Can we get a sorted list from a sorted matrix in $O(n^2)$

I'm confused. I want to prove that that the problem of sorting a $n$ by $n$ matrix i.e. the rows and columns are in ascending order is $\Omega(n^2\log n)$. I proceed by assuming that it can be done ...
12
votes
0answers
159 views

Is the theory of asymptotic bounds finitely axiomatizable?

Let $F$ be the set of functions over real numbers. Consider the structure $M = \langle F, <, \leq, =, \geq, > \rangle$ where the $<, \leq, =, \geq, >$ are defined as asymptotic notions $o$...
16
votes
2answers
345 views

Under what circumstances do $O(n^{a + \epsilon})$ algorithms imply $O(n^{a+o(1)})$ algorithms?

Suppose that, for each $\epsilon > 0$, there is an Turing machine $M_{\epsilon}$ that decides a language $L$ in time $O(n^{a + \epsilon})$. Is there a single algorithm deciding $L$ in time $O(n^{a +...
5
votes
1answer
552 views

$O(m+n)$ really necessary for graph algorithms?

It is standard to express the running time of linear-time graph algorithms as $O(m+n)$ (such as depth-first-search, etc.). For nearly all such algorithms, vertices of degree zero have no effect on ...