# Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

1,357 questions
Filter by
Sorted by
Tagged with
22 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
24 views

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

int[] arr = new int; 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 ...
35 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 ...
47 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 ...
302 views

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

1 vote
81 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 ...
1 vote
27 views

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 vote
50 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!
1 vote
78 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 ...
1 vote
126 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
48 views