# 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 ...
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 ...
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$.
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 ...
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 ...
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 ...
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.
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 ...
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?
20 views

### Run time of pseudo code in big theta notation [duplicate]

I am looking for the run time of the following pseudo code. ...
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})$$ ...
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)$ ...
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 ...
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. ...
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 ...
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$$ ...
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

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