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

learn more… | top users | synonyms

1
vote
2answers
79 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, ...
3
votes
4answers
214 views

Landau Notation: Why is O(f) (not) the set all g < c*f?

I am somewhat confused here about the Landau notations. Let's say we are dealing with function from $\mathbb{N}$ to $\mathbb{R}$. Then we can define $\mathcal{O}(f) = \left\{ g : \mathbb{N} \to \...
1
vote
1answer
46 views

In which O-class does my Θ-result belong?

In a multiple-choice test, I'm asked to solve the recurrence $T(n)=2T(n/2)+n/2$. I've done this using the master theorem: $f(n)=n/2$, $a=2$, $b=2$, so we're in the second case and $T(n)=\Theta(n\log n)...
1
vote
1answer
71 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. ...
5
votes
2answers
76 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,...
4
votes
2answers
262 views

Is $\log(n!)$ in $\Theta(n \log(n))$?

I had two questions on my automated test which I don't understand the answer for. $\log(n!) = \log(n\cdot (n-1)\cdot \cdots \cdot 2\cdot 1) = \log(n)+\log(n-1)+....+\log(1)$. So it is in $O(n\log(...
3
votes
1answer
31 views

Order Notation - Why can't $c$ be in terms of $n$?

For $f(n)$ to be in $O(g(n))$, there must exist a $c > 0$ and $n_0 > 0$ such that $$0 \leq f(n) \leq cg(n) \text{ for all }n \geq n_0\,.$$ I found a solution to a question where my $c$ is in ...
3
votes
2answers
517 views

Why does the square root of n! grow exponentially faster than exponential functions?

I am going through Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al. In the proof of the theorem $6$ of the paper on page 632, the authors go on ...
5
votes
2answers
53 views

Need help understanding a derivation of “witnesses” for a Landau bound

So here's an excerpt from Foundations of Computer Science by Alfred Aho and Jeffrey Ullman[1]. I've also found basically the same material in a few other places, and also in my discrete math textbook, ...
10
votes
3answers
2k views

What does Θ(1) memory mean?

I have the definition of an in-situ algorithm from the professor, but I don't understand it. In-situ algorithms refer to algorithms that operate with Θ(1) memory. What does that mean?
-2
votes
3answers
54 views

Big O relationship between $n^{10\log n}$ and $(\log n)^n$ [duplicate]

I need help with a home task with computer science. the problem is: compare the two complexity functions: $F(n) = n^{10\log n}$ and $G(n) = (\log n)^n$. Which is $O(\ )$ of the other? Which is $\Omega(...
1
vote
3answers
280 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?
1
vote
2answers
81 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 ...
1
vote
2answers
63 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?
0
votes
1answer
34 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 ...
0
votes
2answers
41 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 ...
1
vote
1answer
21 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 ...
1
vote
2answers
82 views

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

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.
4
votes
2answers
72 views

Compare Complexity of Graph Algorithm

Assume I know that there is an algorithm of complexity $ \mathcal{O}( log ( \vert V \vert^2 \vert E \vert ) ) $ for a Graph $G(E,V)$. How do I compare this for example to the complexity of $ \mathcal{...
0
votes
1answer
216 views

Show that if d(n) is O( f (n)) and e(n) is O(g(n)), then d(n)−e(n) is not necessarily O( f (n)−g(n)) [duplicate]

I have this question as an assignment in my Java Algorithms class, and i'm aware that d(n)+e(n) is the same as O(f(n)+g(n)). I dont know why the same doesnt apply to subtracting. Can someone help me? ...
3
votes
1answer
50 views

Why add a +1 to the constant proving an O(n) bound?

I have calculated a running-time function $T(n) = 4 + 4n$, which is $O(n)$. To determine the constant $C$ given by the relation $|T(n)| < C \cdot g(n)$, we take $\qquad\displaystyle \lim_{n \to ...
1
vote
2answers
50 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)$ ...
0
votes
1answer
61 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) ...
44
votes
2answers
6k 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 ...
4
votes
2answers
96 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?
0
votes
1answer
49 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) ...
0
votes
1answer
51 views

Is $\log^2n = O(n)$ or $n = O(\log^2n)$ true?

I'm trying to figure out if: $\log^2n = O(n)$ and $ n = O(\log^2n)$ are true or if one or both are false. So far I've concluded that both are false because if $n = 8$ for the first one, then $\...
10
votes
4answers
328 views

What does $\log^{O(1)}n$ mean?

What does $\log^{O(1)}n$ mean? I am aware of big-O notation, but this notation makes no sense to me. I can't find anything about it either, because there is no way a search engine interprets this ...
2
votes
1answer
95 views

Adding orders of growth

I am confused as to how this is true: O(n log n) + mO(log n) = O((m + n) log n) I understand that O(n) + O(m) = O(n + m). I'm mostly confused as to how to deal with the coefficient preceding O(log n)....
-1
votes
2answers
75 views

What does Big O notation actually specify? [duplicate]

Regarding time complexity I've read conflicting things: 1) That it is worst case. 2) That is average case. For example if I want to know the time complexity for inserting into an arbitrary point in ...
3
votes
1answer
103 views

Big-O Notation Statement True? [duplicate]

Considering functions f and g, is the following true? $ (f \in O(g)) \implies (f \in \Theta(g)) \lor (f \in o(g))$ If not, can you please state an example? Despite thinking hard, i could not find ...
3
votes
1answer
45 views

What's the formal definition of Big-O notation for functions of more than one variable?

For functions of a single totally ordered variable, I already know that $f(n)$ is $O(g(n))$ if and only if $\exists m. \exists c. \forall n. (n \ge m) \rightarrow [ f(n) \le c \cdot g(n) ]$. What I ...
2
votes
1answer
31 views

Understanding multi-variable big O (time complexity)

I have something of this kind: $$(n-1) d m + m + 2m*v+2v^2 + v$$ Where all n,d,m,v are variables. My little knowledge of computational complexity leads to do this kind of approximation: $$ O( (n-1)...
6
votes
2answers
85 views

Why does $2^{O(\log n)} = n^{O(1)}$ hold?

I was recently looking at the article on the P complexity class on Wikipedia. In the section on relationships to other classes, it mentions that P is known to be at least as large as L, giving this ...
1
vote
2answers
60 views

Simplifying an upper O-bound in two variables

I have an algorithm that depends on two input sizes n and m. The complexity breaks down to the following equation: $\frac{nm - 1}{n-1} = O(?)$ Is Big-O of the Formula $O(mn)$ or $O(m)$ because $n$ ...
-1
votes
1answer
14 views

Use of Landau notation for determining bounds [duplicate]

Assume that we have $l \leq \frac{u}{v}$ and assume that $u=O(x^2)$ and $v=\Omega(x)$. Can we say that $l=O(x)$? Thank you.
1
vote
2answers
329 views

Given an analysis of an algorithm, can we get Big-O, Theta, and Omega from this analysis?

If we are given an analysis of an algorithm to be, for example, $5n^3 + 100n^2 + 32n$, can we therefore say that $T(n) = O(n^3)$, and $T(n) = \Theta(n^2)$, and $T(n) = \Omega(n)$, and all of those be ...
5
votes
3answers
474 views

How can a quadratic algorithm be faster than a linearithmic one?

I have to solve the following problem: Al and Bob are arguing about their algorithms. Al claims his $O(n\log n)$ time method is always faster than Bob’s $O(n^2)$ time method. To settle the issue, ...
3
votes
2answers
97 views

Combining these two results into one asymptotic notation

Assume you have two parameters, $N \gg 1$ and $\epsilon < 1$. I have an algorithm (and matching lower bounds) that runs in $\Theta(\epsilon^{-1}+\log N)$ for $\epsilon > N^{-1}$, and $\Theta\...
3
votes
2answers
268 views

Expressing that a function converges to 1 with linear rate using Landau notation

I am working on an algorithm which approximates a certain optimal quantity. The approximation becomes better when the size of the problem ($n$) becomes larger: the difference from the optimum is ...
1
vote
2answers
53 views

Difference between $F(n)=O(n)$ and $F(n)\le O(n)$?

In a research paper I read $F(n) \leq O(g(n))$ and $F(n) \geq \Omega(h(n))$. Isn't this the same as $F(n) = O(g(n))$ and $F(n) = \Omega(h(n))$? Is there a difference?
0
votes
1answer
26 views

Given asymptotic bounds, what can we say about small n?

I am trying to wrap my head around these asymptotic notations. Given $f(n)$ and $g(n)$, one can write $f(n) = \Omega(g(n))$ as shorthand for $f(n) \geq c*g(n), n\geq n_0$. But what happens when $n<...
6
votes
1answer
72 views

What is the name for the complexity class $O(n^{1+\epsilon})$

Sometimes problems can be solved in $O(n^c)$ time for any $c > 1$, but not for $c=1$. Typically this is written as $O(n^{1 + \epsilon})$, since $\epsilon$ is understood to be some small positive ...
3
votes
1answer
32 views

How to state that a complexity bound does not depend on a given parameter size?

I am often ill at ease with Landau (Big O) notation, because it seems often to be abusing mathematical notation. The best example is the use of the equal sign to express a set membership. And this can ...
0
votes
1answer
52 views

Proving that f(N) = N lg N + O(N) implies f(N) = Θ(NlogN)

How do you prove the following? $$f(N)=N\space lg\space N + O(N) \implies f(N) = \Theta(N \space log \space N)$$ Here $lg\space N \equiv log_2\space N$, and $O$ stands for the big-O, and $\Theta$ ...
2
votes
1answer
49 views

Why is f(n) of class O(g(n)) in this graph?

There is a lot of explanation about big O, but I'm really confused about this part. Acoording to the definition of Big-O, in this function $$f (n) \le c g(n), \quad \text{for } n \ge n_0$$ $f (n)$ ...
2
votes
1answer
65 views

Big Theta Proof: May I chose any constant?

I have the following assignment: Prove that $\sum^n_{i=1} i2^i \in \Theta(n2^n)$ My current approach thus far is the following: Since we need to prove $k_1 \cdot n2^n \le \sum^n_{i=1} i2^i \le ...
-1
votes
1answer
48 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 ...
0
votes
1answer
43 views

What is the importance of C in big-Oh notation?

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 ...
0
votes
1answer
41 views

Question about big O notation for function

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