# Questions tagged [landau-notation]

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

256 questions
Filter by
Sorted by
Tagged with
2k views

### big-O and Θ notation subset

I was reading “Introduction to Algorithms” by CLRS and it says Note that f(n) = Θ(g(n)) implies f(n) = O(g(n)) since Θ notation is a stronger notation than O notation. Written set theoretically, we ...
334 views

116 views

### Out of these two algorithms. Is there always an input where A is faster then B? (Big theta notation)

I am currently learning landau notations and am stuck on the following True/False question. What seems a little confusing to me is the use of big-theta notation to describe worst-case run-time. What ...
2k views

### Big-O and not little-o implies theta?

If $f(n)$ is in $O(g(n))$ but not in $o(g(n))$, is it true that $f(n)$ is in $\Theta(g(n))$? Similarly, $f(n)$ is $\Omega(g(n))$ but not in $\omega(g(n))$ implies $f(n)$ is in $\Theta(g(n))$? If not,...
2k views

5k views

### Can I simplify log(n+1) before showing that it is in O(log n)?

Had a question about the following: $$\log (n+1) \in O(\log n)$$ Can the left side be simplified any further or do I need to just go ahead and find a c and n that hold?
337 views

### What is the significance of a Θ-bound on the running time of Mergesort?

While studying algorithm analysis I found that there is something called tight bound and there is some mathematical formula to support it. Given: Mergesort takes $\Theta(n \log n)$ compares to sort ...
589 views

### Why are Complexity Notations Called Asymptotic?

Why do we use the term "asymptotic" in complexity. Although I know what an asymptote is, but what is an asymptote doing here?
635 views

### Complexity of an algorithm with multiple inputs [duplicate]

I've just started reading about the complexity of algorithms, but everywhere I look, it is only defined for one input $n$. For example an algorithm is cubic if its complexity is $O(n^3)$. But what ...
574 views

### Big-O Justification Question

I am trying to justify the big-O order of a runtime complexity by finding a $c$ and $n_0$ that hold for it. Does the left side of the justification need to be one or higher, or can it be any value so ...
320 views

### What are witnesses C and k for an O-bound?

Can someone explain the following about big-O from the textbook to me? (I'm trying to catch up after missing classes due to illness.) Show that $f(x) \in O(x^2)$ where $f(x) = 8x+9$. List the ...
3k views

### What is the Big Theta of $(\log n)^2-9\log n+7$? [duplicate]

How can I find the Big Theta of $(\log n)^2-9\log n+7$? I thought of $(\log n)^2-9\log(n)+7 < c_1(\log n)^2 +7$ or something like this and can't find the right way.
102 views

337 views

### Find Big O using Iteration

I am trying to find Big O of this formula: $T(n)=T(n-1)+2n$ by using iteration however I am stuck on a step. $T(n)=T(n-1)+2n$ I then plugged $T(n-1)$ into the equation so $T(n-1)=T(n-1-1)+2(n-1)$ ...
108 views

### If f(n) = Ω(n) and g(n) = O(f(n)), what do we know about g?

Let f(n) = Ω(n), and g(n) = O(f(n)).Then g(n) = _______. I thought of it this way, since f(n) is Ω(n),then f(n) belongs to the set of functions defined by Ω(n), ie,{n,$n^2$,$n^3$ ....}. So g(n) ...
7k views

### Order of growth definition from Reynolds & Tymann

I am reading a book called Principles of Computer Science (2008), by Carl Reynolds and Paul Tymann (published by Schaum's Outlines). The second chapter introduces algorithms with an example of a ...
333 views

### Is Ω(f+g) = Ω(min(f,g))?

We know that $O(f(n)+g(n))=O(max(f(n),g(n)))$. So can we say that $\Omega(f(n)+g(n)) = \Omega(min(f(n),g(n))$? Then what is $\Theta(f(n)+g(n))$ equal to?
216 views

### Comparing asymptotic notations [closed]

I have a problem P that is said to be O(n^7) in the worst case. I'm asked to agree or not if it is solvable in O(n^9) time. And also I'm asked to agree or not if P cannot be solved faster than Ω(n^7) ...
101 views

81 views

### O(2^n) runs in P… Is this true? [duplicate]

My professor doesn't always know what's actually correct or wrong - he always has to think about it for a very long time and get back to the book and read the book for a long time to answer any of our ...
From the definition of Big Oh, it states that there should be a function $g(x)$ such that it is always greater than or equal to $f(x)$. Or $f(x) \le cg(n)$ for all values of $n > n_0$. What I'm not ...
I'm just starting to learn Big O Notation and I was trying to understand how this function would scale: $\frac{n(n-3)}{4}$ If the function was $n^2$, it would be quadratic, so O(n^2). However, the ...