Questions tagged [landau-notation]
Questions about asymptotic notations such as Big-O, Omega, etc.
271
questions
1
vote
3
answers
105
views
Is $n^{1.03} = \Omega(n \log \log n)$?
We had this problem on our Algorithms final. It threw me off because if $\log$ is $\log_2$ then graphing the function shows this is not true, but if $\log$ is $\log_{10}$ then it looks like it is. How ...
- 127
1
vote
3
answers
102
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 ...
- 73
0
votes
0
answers
67
views
Proving an asymptotic bound with induction
Suppose we want to prove by induction that $f(n) \in \Theta(g(n))$. How should the induction proof be set up? I'm tempted to say that the base case should prove that $f(1) \in \Theta(g(1))$ and the ...
- 257
0
votes
2
answers
133
views
Is $n=\Theta(n^{1+o(1)})$?
Is $n=\Theta(n^{1+o(1)})$?
To me it appears to be true as $n$ tends to infinity $n^{o(1)} =0$.
- 35
4
votes
2
answers
58
views
Finding the constants in Landau notation
I am trying to find the constants $n_0$ and $c$ to show that some given functions belong to the $O(\cdot)$ equivalence class. But, while it seems easy, I am not sure whether I am allowed to do what I ...
- 185
2
votes
1
answer
83
views
Trying to understand the basic about recurrence trees
I have little background on recurrence trees, and I am working on the following exercise:
Exercise. Take $T(n) = 2T(n/2) + 3\log(n)$. Draw the recurrence trees for $n=2$ and $n=4$. What can we ...
- 189
3
votes
2
answers
331
views
Linearity property of summation applied to Big Theta notation (CLRS math background appendix)
Section A.1 of the Mathematical Appendix of the CLRS, the third edition, page 1146, contains the following formula stating linearity property of summation applied to $\Theta$ notation:
$$
\sum_{k=1}^{...
- 133
3
votes
1
answer
174
views
Shifted Big Os. How to say O((n+c)!) = O(n!)?
Suppose an algorithm is $O(n!)$, but we need to run it $n$ times, so the total complexity is
$nO(n!) = O(n \cdot n!) = O((n+1)! - n!) = O((n+1)!)$
Strictly, there is no constant factor that would make ...
- 133
1
vote
2
answers
87
views
Prove that $ln(n)^r \in o(n^p)$ for $p>0$ and $r\in \mathbb{R}$
I am trying to proof $f\in o(g)$
Let be $r,p\in \mathbb{R}$ with $p>0$
We have $f(n)=ln^r (n)$ and $g(n)=n^p$
I have already proofed that $ln(n)\in o(n)$ via l'Hospital
$\lim\limits_{n\to \infty}\...
1
vote
1
answer
42
views
Equivalene of big O definitions (Limit Definition $\Longleftrightarrow$ Quantifier Definition)
I need to proof, that both definitions of the Big 0 notation are equiavlent, but I am not sure if my proof works both ways of the equivalence.
Definitions:
Let f,g be functions.
$f(n)\in \mathcal{O}(...
1
vote
2
answers
61
views
Does a function $f$ exists such that: $f(n-k) \ne \Theta(f(n))$ for some constant $k\geq1$?
I have encountered the following question in my homework assignment in Data Structures course:
"Does a function $f$ exists such that: $f(n-k) \ne \Theta(f(n))$ for some constant $k\geq1$ ?"
...
- 13
1
vote
1
answer
91
views
Why is $\sum_{i=0}^n\sqrt{i}\log_2^2i \geq \Omega(n\sqrt{n}\log_2n)$?
Where $\Omega(f)$ denotes the set of functions with f as lower bound, why is $\sum_{i=0}^n\sqrt{i}\log_2^2i \geq \Omega(n\sqrt{n}\log_2n)$?
How can the function on the left be compared to a whole set?...
- 135
1
vote
1
answer
85
views
Show that $O(\text{max}\{f(n),g(n)\})=O(f(n)+g(n))$
Show that $O(\text{max}\{f(n),g(n)\})=O(f(n)+g(n))$
Can I keep the same constant $c$ in each of the cases?
Consider two cases:
$$1)f(n)>g(n);O(\text{max}\{f(n),g(n)\})⇒O(f(n))\Rightarrow d(n) ≤c��...
0
votes
2
answers
97
views
How do I prove that $3x^3 +2x + 1 $ is $\omega(x \cdot \log x) $
I am trying to answer this question:
$3x^3 +2x + 1$ is $ \omega(x \cdot \log x)$
My question is how to solve this question.
Here is what I have tried so far:
I applied the definition $3x^3 + 2x + 1 ...
1
vote
3
answers
400
views
Prove little o with just the definition
I have been searching for a while now but couldn't find anything about this exact pair of functions with the little $\mathcal{o}$ notation.
Given the functions $f(n) = 2^{n}$ and $g(n) = n!$ I am ...
- 11