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

learn more… | top users | synonyms

4
votes
2answers
64 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 $ ...
0
votes
1answer
76 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
43 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 ...
0
votes
2answers
36 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
55 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) ...
38
votes
3answers
6k views

Not sure if there is a mistake in a computer science book or if I am misunderstanding something

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
87 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
46 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
43 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 ...
9
votes
4answers
277 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
76 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 ...
0
votes
2answers
64 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
101 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
41 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
24 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( ...
6
votes
2answers
73 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
51 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
315 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
346 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
93 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 ...
3
votes
2answers
261 views

Landau notation for functions whose limit is 1 (should big-Oh or big-Omega be used?)

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
52 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 ...
5
votes
1answer
64 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
31 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
40 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
48 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
49 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
46 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
38 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
40 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 ...
2
votes
1answer
24 views

When can we assuredly say that a function is little o of some other function? [duplicate]

I'm trying to determine a function $f(x)$ that is $O(f)$ but not $o(f)$ and also not $\Omega(f)$. Note the $f$ used in the asymptotic notation is not the same as $f(x)$. Originally I thought of ...
3
votes
1answer
69 views

When is the big-O relation preserved under exponentiation?

Suppose that $f, g$ are functions from the positive integers to the positive reals. Under what circumstances will $\log f(n)=O(\log g(n))$ imply $f(n)=O(g(n))$? It's easy to see that this isn't ...
0
votes
2answers
51 views

Why does the Θ-class survive adding a constant only for positive, monotonic, and non-decreasing functions?

I know that for positive monotonically non-decreasing functions, f(n) and g(n), f(n) = O(g(n) + c) entails f (n) = O(g(n)) Why is this always true only for ...
1
vote
1answer
713 views

Is log(n) in complexity class P?

$\log(n)$ is not polynomial; is a problem solvable in $\mathcal{O}(\log n)$ time in P? $n\times \log(n)$ is also not polynomial; is a problem solvable in $\mathcal{O}(n\times \log n)$ time in P? If ...
3
votes
1answer
1k views

Prove transitivity of big-O notation

I'm doing a practice question (not graded HW) to understand mathematical proofs and their application to Big O proofs. So far, however, the very first problem in my text is stumping me wholly. ...
-1
votes
1answer
72 views

Big Omega Counterexample?

I am doing homework to practice for my midterm exam and cannot answer this question. I need to decide whether or not this statement is true of false and either give a proof or counter example. For ...
0
votes
1answer
61 views

Which complexity class $3^{n/3}$

Assuming a problem has complexity $O(3^{n/3})$, Which is its class of complexity ? Despite that it is not as $2^{n}$ ,we can say is an exponential ?
0
votes
1answer
71 views

Big O Asymptotic complexity [duplicate]

I am trying to rank $\log n $, $\log_{10} n $, $n \log n $, $n \log n^2 $, $n^{0.8}$, $\sqrt{n}$ in increasing asymptotic complexity. $\log n $ has base 2 unless specified otherwise. The answer I ...
2
votes
3answers
124 views

Papadimitrou and standard landau notation

This is a homework. I'd appreciate if you didn't give away answer straightaway but instead pointed me to the right direction. From huge majority of sources the definition of $\mathcal{O}(n)$ is: $f, ...
2
votes
1answer
83 views

Is this time complexity quasi-polynomial?

I have been working in the time analysis for an algorithm and finally I got a curve that fits: $O(2^{(\log_2(N)^{2.01})})$ N is the number of elements. I'm right to say the above time complexity is ...
1
vote
1answer
352 views

Subset sum algorithm in O(n³ log n)?

I think that I have found an algorithm which resolve exactly the subset sum problem in $O(N^3)$ in the worst case, only for positive numbers. After my research, I'm lost between all the algorithms ...
2
votes
0answers
32 views

Prove/Disprove that $f(n) + g(n)= O(g(n)*f(n))$? [duplicate]

I would like to know if this statement is true: I thought of giving a counter example by defining: which will give us that but i'm nut sure if it's possible to say that beacuse I suspect that it ...
0
votes
2answers
88 views

Theta estimation of two functions

I'm in a data structures class, and am working on an assignment right now that asks me to find the theta complexity of certain loops. I missed class the day we were introduced to the topic, and ...
1
vote
2answers
47 views

Calculating the runtime for a recursive algorithm [duplicate]

If the runtime of a recursive algorithm could be expressed as $T(n) = \begin{cases}O(1) & n \leq c \\ k * T\left(\frac{n}{k}\right) + \left(k + n * k \right)\end{cases}$ what would be the ...
3
votes
2answers
76 views

Time Complexity $\Theta$ vs. $\Omega$ [duplicate]

If an algorithm has running time of $\Theta(n^2)$, is it possible to have a best-case running time of $\Omega(n)$? Or is the fastest running time only $c n^2$ for some constant factor $c$?
1
vote
3answers
47 views

How to find $c$ and $n_0$ for Big-Oh questions

I understand the theory behind the definition of Big-Oh, but when I try a question, I don't get how you would find the $c$ and $n_0$ values. For example: if $f(n) = n!$ and $g(n) = 2^n$, how would I ...
7
votes
2answers
222 views

Is $n$ times $O(1)$ equivalent to $O(n)$? [duplicate]

I am having a hard time figuring out if $$\sum^n_{i=0} O(1) =O(n)\,.$$ I think it doesn't but I am unable to find a convincing explanation for that, does anyone have an intuitive yet mathematical ...
6
votes
1answer
94 views

Use of Big O Notation in a recent paper by Khot et al

I'm reading a paper about Constraint Satisfaction Problems, specifically "A Characterization of Strong Approximation Resistance", Subhash Khot, Madhur Tulsiani, Pratik Worah (ECCC TR13-075). The ...