Questions tagged [landau-notation]
Questions about asymptotic notations such as Big-O, Omega, etc.
271
questions
1
vote
3
answers
97
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 ...
- 117
1
vote
3
answers
97
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
61
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
118
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
56
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
82
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
187
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}^{...
3
votes
1
answer
172
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
77
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
41
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
59
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
88
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
77
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
94
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
187
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
0
votes
0
answers
18
views
O nation prove with limit theroem? [duplicate]
I'm working on my school homework,even though i found all three of these. It says use limit to compare. I confused , what should i do, i mean its obvious C A B
- 11
0
votes
1
answer
69
views
Big O Tires Question? [duplicate]
My question is regarding the last paragraph of this excerpt from "Cracking the Coding Interview." (For some reason, my table is not formatting here.)
What's the runtime of this code?
...
- 151
0
votes
2
answers
132
views
How to tackle Big O proofs that involve multiple parameters
I am getting more and more familiar with the whole concept of time complexity but I have never encountered an example where more than one parameter is involved. Therefore, is it possible(well, I am ...
- 15
0
votes
1
answer
221
views
Asymptotic growth of a function containing a sum
How to compare the asymptotic growth of a function containing a sum with another function? I'm not sure how I'm supposed to dissolve the sum. Usually I just take the limis of f(x)/g(x). If that fails ...
- 115
0
votes
2
answers
80
views
Is this a correct way to thing about asymptotic notations?
I am reading a book on algorithms. It says that $2n^2+3n+1=2n+\Theta(n)$. For a person like me who has studied some set theory but not from axioms, this notation seems a bit insane. I was wondering ...
guest
2
votes
2
answers
705
views
Induction proofs in Big-O notation
I'm not sure how go about this question:
Prove the following inequality. For a correct proof, we require a value of the constant $c>0$ and an $n \in \mathbb N$, such that $\forall n>N : f(x)<...
- 29
1
vote
1
answer
90
views
How do I simplify $O\left({n^2}/{\log{\frac{n(n+1)}{2}}}\right)$
I'm not very certain about how to deal with asymptotics when they are in the denominator. For $$O\left(\frac{n^2}{\log{\frac{n(n+1)}{2}}}\right)$$, my intuition tells me that it should be treated in a ...
- 113
14
votes
3
answers
5k
views
Is O((n^2)*log(n)) greater than O(n^(2.5))?
I know that $O(n^2\times \log(n))$ is greater than $O(n^2)$, but is $O(n^2\times \log(n))$ greater than $O(n^{2.5})$?
Samuele Bianchi
1
vote
2
answers
1k
views
Summation of asymptotic notation
How can we solve summation of asymptotic notations like given below:
$$
\sum_{k=1}^{n-1} O(n).
$$
- 11
2
votes
1
answer
75
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.
- 21
4
votes
2
answers
279
views
Why is $\sum_{i=1}^n O(i)$ not the same as $O(1)+O(2)+\dots+O(n)$?
The well-known textbook Introduction to Algorithms ("CLRS", 3rd edition, chapter 3.1) claims the following:
$$ \sum_{i=1}^n O(i) $$
is not the same as (I'm not using DNE because the book explicitly ...
Padaca
1
vote
1
answer
54
views
Substitution for Landau's O notation formula
I found the following description when I was reading a paper on computational complexity theory.
This can be done ... in time 2n･poly(logs,n)+2O(logs)c. For s≤2no(1), the runtime is 2n･poly(n).
I ...
- 59
0
votes
0
answers
57
views
which rule can conduct this formula $\log n = O(n^{0.000001})$? [duplicate]
i am learning this post about Big O, which gives this formula
$$\log n = O(n^{0.000001})$$
why is that?
- 588
0
votes
0
answers
20
views
Run time of pseudo code in big theta notation [duplicate]
I am looking for the run time of the following pseudo code.
...
- 115
0
votes
3
answers
357
views
How can i prove this asymptotic comparison? [duplicate]
This is an exercise that's part of my assignment, but it is optional and flagged as a "challenge". I would like to discuss its solution:
Prove that: $$ 27\log{n} + \sqrt{n} = \theta(\sqrt{n})$$
...
- 173
0
votes
3
answers
100
views
If my algorithm has complexity O(n!*n), can I just write O(n!), or do I have to keep it like O(n!*n)?
Just as I asked in the title: if my algorithm has complexity $O(n!\times n)$, can I just write $O(n!)$, or I have to keep it like $O(n!\times n)$?
- 23
2
votes
1
answer
914
views
Proving Big Omega of a polynomial without limits
Here is the definition of $\Omega$:
$f(n) = Ω(g(n))$ iff there exist positive constants $c$ and $n_0$ such that $f(n) \ge cg(n)$ for all $n\ge n_0$.
Here is one theorem:
If $f(n) = a_m n^m + \...
- 23
2
votes
2
answers
61
views
What is wrong with this solution for $\mathcal{O}({\log({n \choose \frac{n}{2}})})$?
In this recitation on MIT OCW, the instructor uses Stirling's approximation to calculate that
$\mathcal{O}({\log({n \choose \frac{n}{2}})}) = \mathcal{O}(n)$.
However, I went through the following ...
- 315
1
vote
1
answer
144
views
Asymptotic relation between n! and (n+1)!
I am having difficulty writing this formally. I know that by L'Hospital's rule we can reduce it to $\lim_{n \to \infty} \frac{n+1}{n}$ which is a constant and hence $n = \theta (n+1)!$. But I am not ...
- 19
1
vote
1
answer
54
views
Are the following Big Oh Notations equivalent?
In the context of Upper bounds computaion and Big Oh Notation, I was wondering if the following could be proved... if they are equivalent.
$\mathcal{O}((log(n))^{-1}) = (\mathcal{O}(log(n)))^{-1}$
$\...
- 141
48
votes
10
answers
11k
views
O(·) is not a function, so how can a function be equal to it?
I totally understand what big $O$ notation means. My issue is when we say $T(n)=O(f(n))$ , where $T(n)$ is running time of an algorithm on input of size $n$.
I understand semantics of it. But $T(n)$ ...
- 591
3
votes
1
answer
12k
views
How come O(n) + O(logn) = O(logn)
How come O(n) + O(logn) = O(logn)?
When talking for example about an algorithm that has two operations. One of them takes O(n) and the other O(logn) and in the end we say that the total complexity is ...
- 47
0
votes
1
answer
61
views
Is this a valid use of big-O notation?
Suppose that $m=O(n^{c+1/2})$ for some real $c>0$ and $x=O(\sqrt{\log m})$. Are the following two computations valid? I understand that I'm abusing notations a bit to get at the desired results.
...
- 103
1
vote
1
answer
1k
views
Introductory explanation of the Big-Oh properties
I've noticed that Big-Oh notation actually has some properties such as summation, product but i couldn't find an introductory explanation for their use or how they can help to solve asymptotic ...
- 173
1
vote
2
answers
194
views
How to prove $\Theta(g(n))\cup o(g(n))\ne O(g(n))$
How to prove $\Theta(g(n))\cup o(g(n))\ne O(g(n))$ ?
Is there a simple example for understanding? Seems there's a gap between $O(g(n))- \Theta(g(n))$ and $o(g(n))$ just from the definition. But I ...
- 31
1
vote
1
answer
35
views
Is this correct in term of big-oh notation: given $g = O(f)$ and $h = O(f)$ can we say $g = O(h)$?
We have two equations $g = O(f)$ and $h = O(f)$ , then can we derive that $g = O(h)$.
I came up with following proof but i dont know it's correct or not.
$$g = O(f)$$
$$g \le c_1*f $$
$$h \le c_2*f $$
...
- 113
1
vote
1
answer
152
views
Asymptotic Notation Analysis
2^n=O(3^n) : This is true or it is false if n>=0 or if n>=1
since 2^n may or not be element of O(3^n)
I need a hint to figure the problem
- 21
0
votes
1
answer
515
views
complexity class of functions [duplicate]
What would these statements mean if f(n) and g(n) are functions over natural numbers?
g(n) is in Θ(f(n)).
and
An algorithm is in the complexity class Θ(f(n)).
- 1
1
vote
3
answers
934
views
What is the constant $C$ in the definition of asymptotic notations?
For example in the definition of $\Theta$:
$f(n) = \Theta(g(n)$ if there exist positive constants $c_1, c_2$ and $n_0$ such that
$$ 0 \leq c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n) \text{ for ...
- 151
0
votes
1
answer
31
views
How can I find $\Theta(log(m_1)+...+log(m_k))$ as related to $m$?
given:
$$m_1+m_2+...+m_k=m$$
How can I find $\Theta(log(m_1)+...+log(m_k))$ as related to $m$?
I know that i can doing that: $O(log(m_1)+...log(m_k))=O(log(m)+...+log(m))=O(k \cdot log(m))$ , but ...
2
votes
1
answer
71
views
Complexity Reduction Analysis
I am struggling to grasp fully grasp complexity reductions, I have this example that I am working through and can not fully comprehend how to determine the complexity of one algorithm given the ...
- 71
0
votes
2
answers
237
views
Two questions about complexity class
Does $2^{n-1}$ and $2^{n}$ share the same complexity complexity class as exponential named as $O(2^n)$? So the former belongs to $O(2^n)$ even though it's one order lower?
What is the name of the ...
- 261
3
votes
1
answer
49
views
Is $T(n) = Ω (n^2)$ the same as $n^2=O(T(n))$?
Question: In the problem below, does proving $T(n) = O(n^2)$ and $n^2 = O(T(n))$ lead to the same result as proving $T(n)=O(n^2)$ and $T(n)=Ω (n^2)$? Which would be the better approach to take? I feel ...
- 133
0
votes
0
answers
153
views
If $f(n)=\omega(h(n))$ and $g(n)=o(h(n))$ then is $f(n)=\Theta(g(n))$?
My question is exactly what the title says. If I have that $f(n)=\omega(h(n))$ and $g(n)=o(h(n))$ hold, then does $f(n)=\Theta(g(n))$ hold as well? My intuition says that the second part is false, but ...
- 144
0
votes
1
answer
664
views
Big O understanding given different input sizes
I have a question about big O notation. Let's say I have 3 algorithms which, for an input of size $n$, have time complexity $O(n)$, $O(n^2)$ and $O(n \log n)$, respectively. Assume that all 3 ...
