Questions tagged [asymptotics]
Questions about asymptotic notations and analysis
1,492 questions
0
votes
1
answer
43
views
What is this asymptotic equivalence called?
Define
$$f\equiv g \iff \exists c,N\quad\forall n>N \quad |f(n)-g(n)|<c$$
What is this called?
It is not the same as
$$f\sim g \iff \forall \epsilon>0 \quad \exists N \quad \forall n>N \...
- 103
1
vote
1
answer
31
views
What does strongly sublinear mean?
I am reading a paper in which it says:
... adhering to the most resricive memory regime, in which the local memory per machine is strongly sublinear in the number of vertices and the total memory is ...
0
votes
0
answers
30
views
What is the difference in number of bit operations in the given expressions using big O notation?
What is the difference in the number of bit operations in the given expressions using big O notation:
$\sum_{i=1}^n i^2$
$\frac{n(n+1)(2n+1)}{6}$
For 1. there are $n$ additing bit operation and $n^2$...
- 1
1
vote
1
answer
68
views
Big O and Omega, how can they be different for a specific case(worst/best)
So I understand that O is an upper bound and omega is a lower bound. I also understand that case is different than bounds, i.e worst case can have O/Theta/Omega different from best case.
My question: ...
- 11
1
vote
0
answers
23
views
Asymptotically optimal strategy for Las Vegas algorithms with unknown run time distribution if you can suspend and resume later
In the paper "Optimal Speedup of Las Vegas Algorithms" Luby, M., Sinclair, A. and Zuckerman, D. give an asymptotically optimal sequences for how many time to run an Las Vegas algorithm ...
- 225
0
votes
3
answers
128
views
Why do we typically give algorithmic complexities through big O?
I mean, we could in principle use $\Theta$, $\omega,o$ and so on but it seems so that $O$ is a favourite in presenting computational complexities. Why?
1
vote
0
answers
82
views
What data structure minimizes the amount of combine operation in point updates and range queries (and having the smallest leading constant)?
Suppose you have an array $a$ of $n$ elements in an set $X$, and a associative binary operation $\circ \ \colon X \times X \rightarrow X$, that can be evaluated in constant time, but is costly (e.g. $...
- 13
0
votes
0
answers
47
views
Is the following algorithm growing at a sublinear or linear rate in time?
I have a number theory algorithm - the details don't matter too much - and it has the following property. Its value is determined by summing up a bunch of sub-functions.
And those sub-functions $f_k(...
- 101
2
votes
1
answer
132
views
Does O(1) average-case imply O(1) generic-case?
We have an algorithm that has an average time complexity of $O(1)$. We wanted to analyse the generic time complexity of the same algorithm. Our coäuthor claimed that $O(1)$ average-case implies $O(1)$ ...
1
vote
0
answers
66
views
How can I optimize the time complexity of a jump-based coin collection algorithm in an array?
I'm working on a problem where I have an array arr of size n, and I need to collect the maximum number of coins by jumping ...
1
vote
1
answer
117
views
Lower Bound on Sorting an Array Where Elements Are at Most $\sqrt{n}$ Positions from Their Sorted Position
Let $A[1 \ldots n]$ be an array of $n$ elements, such that each element is at most $\sqrt{n}$ positions away from its position in the fully sorted array. That is, for every element $A[i]$, its ...
- 385
1
vote
2
answers
82
views
How to interpret phrases of the form "the running time of an algorithm is $O(g(n))$/$\Omega(g(n))$"?
I have been recently reading the classic Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein. However, I'm now a little confused by the interpretations of the phrases "the running ...
- 181
1
vote
0
answers
59
views
Why is this probability $o(1)$ as $m \to \infty$ in a proof of a randomized algorithm for solving $k$-CNF ($k$-SAT) ? A mistake in a famous book?
This is about the proof of Lemma 5.13 in the well-renowned book Motwani R, Raghavan P. Randomized Algorithms. Cambridge University Press; 1995. Access with institutional login: link.
(The lemma is in ...
- 11
1
vote
2
answers
154
views
How to prove $T(n) = 2T(\lfloor\frac{n}{2}\rfloor) + n$ is $\Omega(n\log n)$?
I know how to prove for $O(n\log n)$, but I'm hitting a roadblock with this one. Here's what I've tried:
The hypothesis is that there exists some $c > 0$ so that $T(n) \geq cn \log n $, by assuming ...
- 11
0
votes
0
answers
81
views
How to determine the asymptotics of non-linear recurrence relations?
I have been self-studying the performance of certain algorithms and I have come across a recurrence which I am not sure how to analyse the asymptotic performance.
$
\begin{align}
x_0 &= 0 \\
...
- 51