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

learn more… | top users | synonyms

1
vote
2answers
41 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
285 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
241 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
88 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
257 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
44 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
21 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
60 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
26 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
26 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
45 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
29 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
44 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
36 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
32 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 ...
0
votes
0answers
16 views

State its rate of growth using Θ notation [duplicate]

I have some questions about Analysis of Algorithm Efficiency.Actually, I didn't really understand the theories of this. Please help me to get it guys. My excercise : For each of the following six ...
2
votes
1answer
22 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
56 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
47 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
684 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 ...
2
votes
1answer
484 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
60 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
60 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
65 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
121 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
65 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
272 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
31 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
76 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
39 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
63 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
42 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
205 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
88 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 ...
2
votes
1answer
57 views

Show that 6n^2 + 12n is O(n^2) [duplicate]

I understand how I would do this if the problem were as such $8n + 5$ is $O(n)$ $c>0$ and an integer constant $n(not 0) \geq 1$ such that $8n + 5 \leq cn$ for every integer $n \geq n(not 0)$ we ...
3
votes
3answers
251 views

What do f(x) and g(x) represent in Big O notation?

I have been reading about Big O notation. People writing about Big O often use the terms $f(x)$ and $g(x)$. For instance, I often see people write things like $f(x) = O(g(x))$ or $f(x) \in O(g(x))$. ...
0
votes
0answers
14 views

Least upper bounds on complexities [duplicate]

In popular literature, complexities are usually used in a very imprecise manner, often to describe the runtime performance of an algorithm and denoted with "$O$". My question is about these Landau ...
2
votes
0answers
38 views

Constant in Complexity of SQRT algorithm

this is my first question in CS so I apologize if this question is off-topic. If we use Newton`s Method for finding square root then complexity is $O(M(n))$ (using Wikipedia Notation: $M(n)$ is the ...
0
votes
2answers
69 views

Prove, using only the definition of $O()$, that $2^{\sqrt{x}}$ is not $O(x^{10})$ [duplicate]

Prove, using only the definition of $O()$, that $2^{\sqrt{x}}$ is not $O(x^{10})$. I have been doing a few exercises on Big O and this is the first time I have encountered the variable in the ...
2
votes
3answers
62 views

Are there functions in the same Θ-class that are not linear transformations of each other?

looking for some help, or at least if I'm going the right direction... Are there functions $f$ and $g$ such that $f$ is $O(g)$ and $g$ is $O(f)$ and NO constants $c_1$ and $c_2$ exist for which ...
3
votes
1answer
168 views

Can a Big-Oh time complexity contain more than one variable?

Let us say for instance I am doing string processing that requires some analysis of two strings. I have no given information about what their lengths might end up being, so they come from two distinct ...
-1
votes
1answer
24 views

Question Concerning Big-O Notation

A couple of questions: When choosing $C$ do I have to choose an integer? I see nothing in my definitions preventing fractions, but I haven't seen any in anything I've looked up, either Given ...
3
votes
2answers
67 views

Origins of misconception about using equality signs with Landau notation

From "Misconception 1" from Søren S. Pedersen's blog, and as many have seen before, a major misconception in Big-O (and others) notation is to say a function is "equal" to Big-O of some other ...
2
votes
1answer
70 views

Which article in front of O(.), Ω(.), …?

Writing a survey, I am confronted to a very difficult and -- I dare say -- deep issue: I have many sentences mentioning or stating results of the form "a $\Omega(\sqrt{n})$ lower bound", or "a ...
3
votes
3answers
399 views

What is the notation for bounding running time in worst case with concrete example resulting in that worst case running time

I know that Big O is used to bound worst case running time. So an algorithm with running time $O(n^5)$ means its running time in worse case is less than $n^5$ asymptotically. Similarly, one can say ...
1
vote
1answer
58 views

Why are different logarithms in the same Θ even thought their difference diverges?

As I have read in book and also my prof taught me about the asymptotic notations The general idea I got is,when finding asymptotic notation of one function w.r.t other we consider only for very large ...
3
votes
3answers
234 views

Can someone clarify landau symbols definition please?

I'm more or less familiar with the landau symbols, most specifically in computer science for complexity, however I was wondering if someone could clarify a bit for me. I'll just mention that I know ...
3
votes
2answers
152 views

Is Big-Oh notation preserved under monotonic functions?

I was just looking at the big-Oh notation. I wanted to know if the following is true in general $$f(n)=O(g(n)) \implies \log (f(n)) = O(\log (g(n)))$$ I can prove that this is true if $g$ is ...
8
votes
2answers
223 views

Why doesn't $O(1)+O(2)+\cdots+O(n)$ have an interpretation?

In CLRS (on pages 49-50), what is the meaning of the following statement: $\Sigma_{i=1}^{n} O(i)$ is only a single anonymous function (of $i$), but is not the same as $O(1)+O(2)+\cdots+O(n)$, ...