# Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

1,361 questions
Filter by
Sorted by
Tagged with
1 vote
26 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 ...
• 11
41 views

### If $f \in \mathcal{o}(g)$, does $f \circ g \in \mathcal{o}(g \circ f)$?

It's a widely known fact that $\lambda n. \left\lfloor \lg n! \right\rfloor \in \mathcal{O}(\lambda n. \left\lfloor \lg n \right\rfloor!)$. Is it also true (I tried and haven't found a counterexample ...
• 115
65 views

### Complexity of multiple $O(\log N)$ is $m*O(\log N)$ or $O(\log N)$?

Assume we have an algorithm consists of several (assume m and m<10) different algorithms each of which has time complexity $O(\log N)$. Is the time complexity of our algorithm is $m*O(\log N)$ or ...
• 151
1 vote
49 views

### Difference between "almost-linear" and "quasilinear" time complexities

In some works, such as the recent maxflow paper, there is reference to an "almost-linear" complexity, which typically refers to a complexity of $O(n^{1+o(1)})$. This is similar to the notion ...
• 43
1 vote
35 views

### Contradicting asymptotic analysis in recurrence equation?

I'm trying to solve the recurrence equation from CLRS ed 2. $$T(n) = 2T(\sqrt{n}) + 1$$ The question says the solution should be asymptotically tight, but at first I didn't read it and solved it ...
1 vote
27 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 ...
• 11
39 views

### Solve Recurrence T(n) = 4T(n/4) + n*[log(n)]^2

I am trying to solve T(n) = 4*T(n/4) + n*[log(n)]^2 I decided to use Master Theorem so I found a,b=4 and logb(a)=1. I thought that 3rd case is the solution but I ...
49 views

### A little confusion with Big Theta time complexity

I came across one Big Theta expression: Here I am thinking this expression to be valid. But please correct me as the answer doesn't goes in the same way. As per definition of Big Theta.. any function ...
305 views

• 165
1 vote
77 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 ...
85 views

1 vote
84 views

### Prove recurrence T(n) = 2T(n/2) + n/lgn is O(nlglgn) using Substitution Method

Prove that $T(n) = 2T(\frac{n}{2}) + \frac{n}{\log_2n}$ is $O(n\log_2\log_2n)$, where $T(1) = Θ(1)$. I tried to form the Induction Hypothesis but didn't succeed in choosing the right one. Try 1: If we ...
• 45
1 vote
27 views

• 53
28 views

### Why are we allowed to ignore constant factors of $g(x)$ in recurrence while they are important in solving the recurrence?

I'm trying to learn about asymptotic notations and recurrences and I use MIT 6.042 Mathematics for Computer Science as my resource. and I have some questions about the Professor's talks. He said: ...
• 1
1 vote
51 views

90 views

### n! and 2^(n^2); which one grows faster

I can't figure this out; is $2^{n^2}=O(n!)$ or is it the other way around? Any help is appreciated!
• 105
1 vote
93 views

### Subtraction on Big Theta notation

This is a question I got for an assignment, and I have been stuck on it for the past few days. Prove that $\Theta(n)+\Theta(n-1) = \Theta(n)$ Does it follow that $\Theta(n) = \Theta(n)-\Theta(n-1)$ I ...
27 views

### Sum of asymptotic notations

Let's consider a function $f \in \Theta(h)$ and a function $g \in \omega(h)$, what could I conclude about the sum $f + g$? Since $f \in \Theta(h)$ I think about $f$ as if it grows just like the ...
• 13
1 vote
127 views

### Θ, O and Ω, and how they relate to each other as subsets

I am trying to understand how $\Theta(n)$, $O(n)$, and $\Omega(n)$ relate to each other as sets and want to make sure I'm on the right track. I get that $Θ(n) \subseteq O(n)$ since $Θ(n)$ is stronger ...
1 vote
What is the correct asymptotic lower bound for $f(n) = 3n^2 + 2n$? I was thinking that the lower bound would simply be $\omega(n) = cn^2 + n$, for the constant $c = 3$ and integer $n \ge 1$. Indeed, $... 2 votes 1 answer 94 views ### Asymptotic height of d-ary heap I know that the height of a$d$-ary heap on$n$nodes is$\lceil (\log_d (n(d-1) + 1) - 1)\rceil$, but I was wondering how to justify that that's$\Theta(\log_d n)$? I know the definition of$\Theta, ...
Consider g a function of n: $g(n)$. Knowing that the function $f(n) \in Θ(g(n))$ and the function $h(n) \notin O(g(n))$, could we conclude anything, related to it's asymptotic behaviour, about \$f(n) + ...