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
220 views

• 498
1 vote
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$ ...
1 vote
43 views

### Shell sort algorithm analysis

Given this Shell sorting algorithm implementation: ...
• 21
1 vote
35 views

### Shell algorithm knuth sequence time complexity analysis

Given this shell sort algorithm implementation: ...
• 21
1 vote
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 ...
• 121
1 vote
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 ...
1 vote
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 ...
• 257
1 vote
69 views

1 vote
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 ...
• 155
1 vote
42 views

• 83
1 vote
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 ...
• 5,862
1 vote
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 ...
1 vote
55 views

1 vote
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(\...
• 1,529
1 vote