Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

140 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6 votes
0 answers
220 views

Are there master theorems that deal with parameters of the form $n-c$?

While thinking about this question on a recurrence I checked out some stronger master theorems. Unfortunately, they do not seem to apply because terms $\qquad\displaystyle T(n) = \dots + T(n-1) + \...
Raphael's user avatar
  • 72.5k
3 votes
0 answers
100 views

Induction pitfalls with O notation and recursion

I read the following in CLRS 3rd Ed: I'm not sure I understand exactly how to avoid this pitfall. How would one know that the $\mathcal{O}$ notation in this case grows with $n$ and is thus not ...
Amelio Vazquez-Reina's user avatar
3 votes
0 answers
29 views

Bit complexity of computing the sign of an expression evaluated at an algebraic number

I have a univariate polynomial $F(t)\in \mathbb{Z}[t]$ of degree $d$ and maximum bitsize of coefficients equal to $\tau$ and $G(t) \in \mathbb{Z}[t]$ of degree $d^2$ and maximum bitsize of ...
asdf's user avatar
  • 131
3 votes
0 answers
54 views

Worst Case Analysis of a Multivariate Recurrence of a Graph Algorithm

I have a graph algorithm that runs in: $$ T(n, m) = \begin{cases} c_1 & n \leq 2 \lor m = 1\\ T(n - i,\ m - j - k) + T(i, k) + c_2 m + c_3 n & m \leq (n-i)i\\ T(n - i,\ m) + T(i, m) + ...
ryan's user avatar
  • 4,511
3 votes
0 answers
400 views

How to find big-O for an in-place perfect shuffle algorithm

I've found a simple algorithm to interleave two halves of an array in place. It involves swapping the first 1/2 of the items into the correct place, then unscrambling the permutation of the 1/4 of ...
AShelly's user avatar
  • 161
3 votes
0 answers
168 views

Name for function in big O but not in little o?

Let $f(n) = O(g(n))$, but not $f(n) = o(g(n))$. That's a nice property, because it means that we cannot replace $g(n)$ with a substantially smaller function. Is there a name for this choice of $g(n)$? ...
gnasher729's user avatar
  • 30.4k
3 votes
0 answers
59 views

Examples of algorithms with low spacetime complexity

When running a data center, one of the cost metrics you might care about is "ram seconds". For example, an algorithm that holds 1 MB of memory for five minutes consumes 300 million ram seconds. A ...
Craig Gidney's user avatar
  • 5,862
3 votes
0 answers
1k views

Node potentials of minimum cost flow successive shortest path algorithm

I have a simple directed graph $G(V,E)$ that has a source $s$ and sink $t$. Each edge $e$ of $G$ has positive integer capacity $c(e)$ and positive integer cost $a(e)$. I am trying to find the minimum ...
Wakaka's user avatar
  • 231
2 votes
2 answers
193 views

Quickly obtaining sums of sets of numbers

We are given a set of $n$ bits, call them $a_1$, $a_2$,...,$a_n$. We are also given a set of $m$ sums, where the sums $s_1$, $s_2$,...,$s_k$,...,$s_m$ are given as sums of some of the bits. For ...
Matt Groff's user avatar
2 votes
0 answers
45 views

Asymtotic bound for recurrence of $T(n)=2T(n/2)+ \sum_{i=0}^{n} (i+2)^2$ using substitution

What can be an initial guess for finding the tight asymptotic bounds of $T(n)=2T(n/2)+ \sum_{i=0}^{n} (i+2)^2$ using substitution method?
Yashar's user avatar
  • 21
2 votes
0 answers
31 views

Useful conditions for proving super polynomial lower bound for some kind of recurrences

Given a recurrence of the form $\forall n,m.\ \ T(n,m)=\begin{cases}1,&,m=1\\\sum_i{T(n_i,m_i)}&,\text{else}\end{cases}$ Note: both $n_i$ and $m_i$ are dependent on $n,m$ so they should have ...
Dudi Frid's user avatar
  • 181
2 votes
0 answers
64 views

Can there be functions in o(1) in algorithm analysis?

I saw a similar question to this one here but it's not quite the same as mine: Is every algorithm's complexity $\Omega(1)$ and $O(\infty)$? I've just started a course in data structures and ...
Or Bairey-Sehayek's user avatar
2 votes
0 answers
2k views

Can factorial be done in O(1) and proof?

The typical way to compute the factorial would take $O(n)$ because it calls itself recursively. However, there are many other ways to compute the factorial function based off the gamma function, ...
mtheorylord's user avatar
2 votes
0 answers
22 views

Is variance taken into account when algorithm analysis is performed?

Silly question. I was wondering if the measure of "variance" is taken into account when the analysis of an algorithm is performed (asymptotic). In general best-case,worst-case,average-case are taken ...
user8469759's user avatar
2 votes
0 answers
385 views

Amortized time complexity of append on a dynamic array that resizes according to geometric base 1.25?

I'm trying to prove that the amortized time complexity of appending to a dynamic array that resizes in accordance with capacity = $N$ to $N+\lceil{\frac{N}{4}}\rceil$ is $O(1)$. I'm assuming that ...
robbentheking's user avatar
2 votes
0 answers
776 views

How to find all paths with n-distance from a node in a graph with cycles?

I have to find all the paths that have some n-distance from a start node. The destination node is not given. It seems that this problem is very hard to solve because in this scenario I am working with ...
darophi's user avatar
  • 121
2 votes
1 answer
983 views

Solving T(n) = 2T(n/3) + 2 T(2n/3) + n

The goal is to get big $\Theta$ for $$T(n) = 2T\left(\frac{n}{3}\right) + 2T\left(\frac{2n}{3}\right)+n$$ I tried two approaches, but both failed: Recursion tree. We see that $$\begin{align} \sum_{...
Retired account's user avatar
1 vote
0 answers
88 views

What is the difference between $O$ and $\widetilde{O}$?

We know that $\widetilde{O}(f(n))$ — $O$ with a tilde above it — which means $O(f(n) \text {polylog}(f(n)))$, i.e., $O(f(n) (\log f(n))^k)$ for some $k$. Also I have seen in Wikipedia that $n2^n=\...
A. H.'s user avatar
  • 498
1 vote
0 answers
25 views

Upper bound via standard manipulation in proof of semi-private learning

I have been reading a paper on private learning [1]. In the proof of lemma 3.3. they claim that $$ 2\left(\frac{2e n_\text{pub}}{d}\right)^{2d}e^{-\alpha n_\text{pub}/4} $$ is upper bounded by $\beta$ ...
TheCollegeStudent's user avatar
1 vote
0 answers
43 views

Shell sort algorithm analysis

Given this Shell sorting algorithm implementation: ...
Kim's user avatar
  • 21
1 vote
0 answers
35 views

Shell algorithm knuth sequence time complexity analysis

Given this shell sort algorithm implementation: ...
Kim's user avatar
  • 21
1 vote
1 answer
78 views

The value of $r$, with $r≤ b$, that minimizes the expression $(b/r)(n+2^r)$ in the analysis of the radix-sort algorithm

In chapter 8 of the book "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein, lemma 8.4 is proved. (my question is after the proof of the lemma) Given $n$ $b$-bit numbers ...
emacos's user avatar
  • 121
1 vote
3 answers
99 views

Upper bounding this expression

I need to prove that the following expression is $\mathcal O(n \log n)$ with the substitution method: $$ T(n) \leq 3\log n + n + \frac{6}{n}\sum^{n - \frac{\log n}{3}}_{i=\frac{\log n}{3}} T(i)$$ This ...
joeren1020's user avatar
1 vote
0 answers
51 views

Runtime of this algorithm

I have an algorithm with running time that satisfies $$ T(n) \leq n + \frac{1}{n}\sum^{n-1}_{i=0}(T(i) + T(n-i)),$$ and $T(0) = 0$. I was able to show that $T(n) = \mathcal O(n\log n)$ with a leading ...
Keio203's user avatar
  • 257
1 vote
0 answers
69 views

Is it true that: $f\notin o(g)$ implies $\exists c>0: f > cg$ infinitely often

My (attempt at a) proof is as follows: $f\in o(g)$ means that $\forall c>0 \exists n_0 \forall n\geq n_0: f(n) \leq cg(n)$. Now taking the complement we get: $\exists c>0 \forall n_0 \exists n\...
RoSv's user avatar
  • 11
1 vote
0 answers
66 views

Algorithms with different upper and lower bounds

I am preparing a list of algorithms for which big theta expression for (worst case) runtime is not known. This is for a class to demonstrate the point that tight analysis of an algorithm may not be ...
Mudi's user avatar
  • 11
1 vote
0 answers
45 views

Does creating an array count as a primitive operation under the RAM model?

int[] arr = new int[10]; Would this count as a single primitive operation under the RAM model or would it be 10 operations as we are allocating 10 memory locations ...
Parzival's user avatar
1 vote
0 answers
201 views

Given T(1)=1 and $T(n) = 3T(n/4) + cn^2$, does it make sense to yield $T(2)=T(1)+c2^2$?

Section 4.4 of "Introduction to Algorithms, 3rd Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein" illustrates how a recursion tree provides a good guess ...
JJJohn's user avatar
  • 588
1 vote
0 answers
81 views

Recursive algorithm running time?

I would like your opinion on how to detect the T(n) (Running Time) for the following recursive algorithm. Charm is an algorithm for discovering frequent closed itemsets in a transaction database. A ...
Danilo Giovannico's user avatar
1 vote
0 answers
92 views

Recursion analysis using Master Theorem

I have the following algorithm: ...
Mouvre's user avatar
  • 131
1 vote
0 answers
40 views

Conditions on a and b in Master theorem

Should the $a$ and $b$ in Master theorem be integers or they can be rational numbers? I think $a$ must be an integer but $b$ can be rational.
Emad's user avatar
  • 411
1 vote
3 answers
95 views

What are the guidelines/tips for calculating the complexity of a chained-recursive function?

Any help will be appreciated, as I wasn't able to find much about it online in the last few days and I can't seem to write a suitable recurrence relation for this kind of functions.. Are there any ...
DolevBaron's user avatar
1 vote
0 answers
97 views

Asymptotic running time function's domain

I am reading CLRS and have uncertainty in asymptotic running time of algorithms. In CLRS, it is said, The notations we use to describe the asymptotic running time of an algorithm are defined in terms ...
user avatar
1 vote
0 answers
98 views

Constant in Substitution method for recurrence

The solution for solving the following recurrence with the substitution method involves adding the a constant inside the recurrence, which is confusing to me. This is question 4.3-2 in the CLRS ...
Frantz Paul's user avatar
1 vote
0 answers
50 views

Complexity Values for Specific Code/Functions

(1) Assume a function $f:\mathbb{Z^+}\rightarrow\mathbb{R}$ that's defined in a way that utilizes, say, eight basic computations, including addition, subtraction, division, multiplication, (positive ...
u220e's user avatar
  • 11
1 vote
0 answers
33 views

Heuristics for maximizing the performance for a given complexity

I often have to balance the computational requirement of each qualitatively different module of my algorithm. So, I'm using this heuristics for maximizing the performance for a given complexity, but I ...
Math.StackExchange's user avatar
1 vote
0 answers
46 views

Big O notations of some functions

What is the big-O notation of the following functions : $\displaystyle\sum_{i=1}^n \left(\begin{array}{c} n-1\\ i \end{array}\right)\\\\ \displaystyle\sum_{i=1}^{n} \sum_{j=1}^{n-i}(3j)\\\\ n^{\...
Eliran Turgeman's user avatar
1 vote
0 answers
137 views

How to find the asymptotic bit cost

I know from a general point of view what big O notation is. I have taken an algorithms class before that was all implementations and did well. I am now in an algorithms class that is mostly theory and ...
Joff's user avatar
  • 155
1 vote
0 answers
42 views

Prove that for all functions g: N -> R>=0, and all numbers a in R>=0, if g in Omega(1) then a + g in Theta(g)

Here is a more readable version of the question: Prove that for all functions $g: \mathbb{N}\to\mathbb{R}^{\geq 0}$, and all numbers $a \in \mathbb{R}^{\geq 0}$, if $g \in \Omega(1)$ then $a + g \in \...
user avatar
1 vote
0 answers
106 views

Proving asymptotic bounds

I'm confused if the following approach is mathematically correct Suppose I have to prove $(\log n)! > n^a$, where $a$ is a constant I can assume $n = 2^k$ which leads to $k! > c^k$, where $c = ...
Yueor's user avatar
  • 83
1 vote
0 answers
51 views

Circuit depth of computing the continued fractions of a rational number

If you want to convert a rational number into its continued fraction, what is the circuit depth of this process, in terms of the total number of bits of input? I was reading through some notes which ...
Craig Gidney's user avatar
  • 5,862
1 vote
0 answers
64 views

Quick Clarification Question about Time Complexity in CLRS

I'm reading about the Hiring Problem in "Introduction to Algorithms" and read Interviewing has a low cost, say $c_i$, whereas hiring is expensive, costing $c_h$. Letting $m$ be the number of ...
Noah Stebbins's user avatar
1 vote
0 answers
55 views

Cuckoo hashing with a stash: how tight are the bounds on the failure probability?

I was reading this very good summary of Cuckoo hashing. It includes a result (page 5) that: A stash of constant sizes reduces the probability of any failure to fall from $\Theta(1/n)$ to $\Theta(...
Daniel-耶稣活着's user avatar
1 vote
0 answers
123 views

What are the asymptotic bounds (upper bound on time complexity) of the following function?

I am trying to find the upper bound on time complexity of the recursive function defined by the following equation: $$Q(t) = \sum^{N}_{i=1} q_i \big(g_i^{\frac{1}{m-1}} + Q(t+1)^{\frac{m}{m-1}}\big)^{\...
mehdi's user avatar
  • 11
1 vote
0 answers
125 views

Can I say θ(g(n)) is the intersection of Ω(g(n)) and O(g(n))?

Let's say Ω(g(n)) be a set representing the lower bound and O(g(n)) be another set representing the upper bound for some function f(n). Can I say that θ(g(n)) is the intersection of these two sets? ...
rsonx's user avatar
  • 281
1 vote
0 answers
37 views

What is the runtime of Quantum Fourier Sampling

I have seen estimates for the runtime of Shor's Algorithm,, which relies on Quantum Fourier Transformations. What is the runtime of those transformations themselves? Either big-O or more accurate ...
Pro Q's user avatar
  • 115
1 vote
0 answers
149 views

Order of growth: substitution of monotonically increasing functions

One strategy for ordering the growth of functions involves substitutions when comparing functions using the limit as $n$ goes to infinity comparing two equations using the following rule. $$ \lim_{n\...
zachsmthsn's user avatar
1 vote
0 answers
72 views

Verifying that $f(x) \leq Cg(x)$ for $x \geq k$

I'm revising for a test and having problems with a past question. It states that $f(x)=5x^2+4x+3$ is $O(x^2)$ and has a series of sub-parts asking if particular values of $C$ and $k$ (e.g., $C=12$, $k=...
Christoffer's user avatar
1 vote
0 answers
909 views

Why do we count the ceils and floors in recursive functions?

When we solve the recursive functions using substitution method, the impact of ceil and floor functions is trivial when the size of the input is large enough. For example the answer of $$ T(n) = T(\...
M a m a D's user avatar
  • 1,529
1 vote
0 answers
75 views

Divide-and-conquer algorithm to takes a set of itineraries and returns desirable itineraries

I've been given a question that states I will be given a set of itineraries, which are basically tuples in the form (cost, time) for airplane flights. An itinerary dominates another itinerary if its ...
Qwurticus's user avatar
  • 111