# Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

1,038 questions
Filter by
Sorted by
Tagged with
17 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 ...
45 views

10k views

55 views

### Show that the union of Θ and o is not O

Show that: $\Theta(n\log n)\cup o(n\log n)\neq O(n\log n)$ I tried to start this in many ways but I don't really know how... intuitively isn't $\Theta \cup o = o$? So that would mean that I would ...
36 views

### Find function that satisfy the relation

Can you find the function that satisfy the relation? $$f(n) = \Theta(g(n)), f(n) = o(g(n))$$
33 views

### Difference Between $n^{\Omega{(1)}}$ and $\Omega{(n)}$ [closed]

I am not sure about the difference between $n^{\Omega(1)}$ and $\Omega(n)$. It seems to me that the only difference is that $n^{\Omega(1)}$ can contain some sublinear functions, i.e., $n^{\frac{1}{2}}$...
45 views

### Big theta of function with multiple types of n [duplicate]

I have the following function: $\displaystyle\frac{n \cdot 7^n+\frac{8}{n!}}{(n+7) \cdot 7^n}=\Theta(1)$ I don't how they come to this. What is the proper way to analyse a function to theta notation?...
38 views

### Is log(n) equivalent to (log(n))^x for big-O analysis?

My professor noted that we could treat any logarithmic function with an exponent as equivalent to log(n) for the purposes of big-O analysis. ie. $(n log(n) + 1)^2 + (log(n) + 1)(n^2 + 1)$ From the ...
75 views

### Solving $T(n) = 2T(n/2) + T(n-1)/\log n$

I am interesting in the asymptotic rate of growth of the following recursion: $$T(n) = 2T(n/2) + \frac{T(n − 1)}{\log n},$$ with base case $T(1) = 1$. I'm having trouble of solving this recurrence ...
67 views

### When are log complexities considered equivalent?

Would we consider $O(\log_2(n))$ to be the same complexity as $O(\log_2(n-1))$? Why or why not? I'm specifically wondering about how the number we take the log of affects the time complexity.
31 views

### Splitting summations?

From CLRS Introduction to Algorithms, Appendix A, page 1152. They discuss a method called "Splitting Summations", where they split the summation and bound each term separately. For example, ...
61 views

### How to mathematically prove that a relation T(n)=T($\sqrt{n}$)+c is O(log(log(n))?

following question, I understood the intuition behind how cutting down the size of input by square root on each iteration leads to O(log(log(n))) complexity. I tried to derive it on paper. Let T(n) =...
46 views

### Simplifying this expression with big O when several variables are involved

I have an algorithm which depends on three variables an where the running time is in $\mathcal{O}(m+2 m\cdot n\cdot p+p\cdot(n+m))$ and I would like to simplified it. I proceeded as follows : \begin{...
54 views

### Is $(\sqrt{n})!=Θ(\sqrt{n}^{\sqrt{n}})$?

I would like to express $(\sqrt{n})!$ in terms of $Θ()$ notation. My approach is the following: $$(\sqrt{n})!=f(n)\Leftrightarrow$$ $$\log(\sqrt{n})!=\log(f(n))$$ Now from Stirling's approximation ...
I am doing a project in analysis of algorithm and I have been looking all over for something more complex than Perlin Noise is $O(n \cdot 2^n)$ because of the doubling in $n$ dimensions and array ...