Questions tagged [asymptotics]

Question 1

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 \...

Question 2

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 ...

Question 3

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$...

Question 4

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: ...

Question 5

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 ...

Question 6

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?

Question 7

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. $...

Question 8

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(...

Question 9

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)$ ...

Question 10

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 ...

Question 11

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 ...

Question 12

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 ...

Question 13

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 ...

Question 14

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 ...

Question 15

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 \\ ...

Stack Exchange Network

Questions tagged [asymptotics]

What is this asymptotic equivalence called?

What does strongly sublinear mean?

What is the difference in number of bit operations in the given expressions using big O notation?

Big O and Omega, how can they be different for a specific case(worst/best)

Asymptotically optimal strategy for Las Vegas algorithms with unknown run time distribution if you can suspend and resume later

Why do we typically give algorithmic complexities through big O?

What data structure minimizes the amount of combine operation in point updates and range queries (and having the smallest leading constant)?

Is the following algorithm growing at a sublinear or linear rate in time?

Does O(1) average-case imply O(1) generic-case?

How can I optimize the time complexity of a jump-based coin collection algorithm in an array?

Lower Bound on Sorting an Array Where Elements Are at Most $\sqrt{n}$ Positions from Their Sorted Position

How to interpret phrases of the form "the running time of an algorithm is $O(g(n))$/$\Omega(g(n))$"?

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?

How to prove $T(n) = 2T(\lfloor\frac{n}{2}\rfloor) + n$ is $\Omega(n\log n)$?

How to determine the asymptotics of non-linear recurrence relations?

Hot Network Questions