# Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

1,098 questions
Filter by
Sorted by
Tagged with
1k views

### Can someone clarify landau symbols definition please?

I'm more or less familiar with the landau symbols, most specifically in computer science for complexity, however I was wondering if someone could clarify a bit for me. I'll just mention that I know ...
78 views

### Asymptotic Runtime of Interrelated Functions

I have two functions $S$ and $T$ which are interrelated and I want to find the asymptotic worst case runtime. The fact that they are interrelated is stumping me... How would I find the asymptotic ...
320 views

### Why is this $f(n) \leq 6n^3 + n^2 \log n \in O(n^3)$ for all $n \geq 1$?

I'm currently studying for an algorithms midterm in about 2 days and am reading from the beginning of the course, and stumbled upon this when I actually looked at the examples. The question equation: ...
1k views

### Number of times statement is executed in complex nested loop

I am trying to find out how many times the "statement" is executed by finding its formula based on these loops: ...
2k views

### Why is a sequence of n Push, Pop, Multipop operations O(n²)?

From "Introduction to Algorithms" by Cormen, Leiserson, Rivest, Stein, Third Edition, page 453: Let us analyze a sequence of $n$ Push, Pop, Multipop operations on an initially empty stack. The ...
2k views

### Is there an NP-complete problem that can be solved in $O(n^{\log n})$ time?

I'm following an online course which has the following (multiple-choice) quiz question: Which of the following statements cannot be true, given the current state of knowledge? Some NP-...
111 views

### what is the time complexity for an algorithm that operations to complete grows by 4 when doubling the input length?

I'm working on an algorithm and I'm trying to figure out its time complexity given the operations it takes to complete a input set of specific length, I have been testing the algorithm with varying ...
532 views

### how to prove that nlogn is not Θ(n) without using limits?

i'm studying an algorithms designing and analysis , and i've question about Big-theta how can i prove that nlogn is not Θ(n) without using limits ?
2k views

253 views

### Time Complexity $\Theta$ vs. $\Omega$ [duplicate]

If an algorithm has running time of $\Theta(n^2)$, is it possible to have a best-case running time of $\Omega(n)$? Or is the fastest running time only $c n^2$ for some constant factor $c$?
2k views

638 views

### Complexity of k-way merge with log n arrays of size n / log n

I'm designing an in-place sorting algorithm to sort a collection of size $n$. Near the end of the sorting, it may end up with with $\log{n}$ sorted sub-sequences of size $\frac{n}{\log{n}}$. At this ...
### Asymptotic estimate for $\sum_{k=1}^{N} {\frac{1}{k^2 H_k}}$
I am working on finding the asymptotic estimate for $$\sum_{k=1}^{N} {\frac{1}{k^2 H_k}}.$$ All I know is that ${\frac{1}{k^2 H_k}}$ is convergent because $${\frac{1}{k^2 H_k}}<\frac{1}{k^2}$$ and ...
I faced some problem that involves arithmetic over asymptotic functions. These are as follows: Let f(n)= Ω(n), g(n)= O(n) and h(n)= Ѳ(n). Then [f(n). g(n)] + h(n) is: (a) $Ω(n)$ (b) $O(n)$...