Questions tagged [landau-notation]

Questions about asymptotic notations such as Big-O, Omega, etc.

271 questions
Filter by
Sorted by
Tagged with
1 vote
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
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 ...
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
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
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
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
187 views

94 views

1 vote
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
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})$?
1 vote
1k views

Summation of asymptotic notation

How can we solve summation of asymptotic notations like given below: $$\sum_{k=1}^{n-1} O(n).$$
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
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 ...
1 vote
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
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
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
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
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)$?
914 views

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

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

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