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

learn more… | top users | synonyms

0
votes
1answer
36 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
60 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
114 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
49 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
190 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
62 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
32 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
38 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
33 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 ...
6
votes
2answers
169 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
66 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
51 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 ...
2
votes
3answers
133 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
13 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
36 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
67 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
60 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 ...
2
votes
1answer
97 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
22 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
61 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
66 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
368 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
50 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
2answers
192 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 ...
2
votes
2answers
100 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
192 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)$, ...
1
vote
3answers
52 views

Confusion with the Running Time of an algorithm that finds duplicate character

I have the following simple algorithm to find duplicate characters in a string: ...
0
votes
3answers
429 views

Why is constant always dropped from big O analysis?

Suppose I have an algorithm that has a performance of $O(n + 2)$. Here if n gets really large the 2 becomes insignificant. In this case it's perfectly clear the real performance is $O(n)$. However, ...
3
votes
1answer
61 views

O(f) vs O(f(n))

I first learned about the Big O notation in an intro to Algorithms class. He showed us that function $g \in O(f(n))$ Afterwords in Discrete Math another Professor, without knowing of the first, told ...
3
votes
4answers
234 views

Why does merge sort run in $O(n^2)$ time?

I have been learning about Big O, Big Omega, and Big Theta. I have been reading many SO questions and answers to get a better understanding of the notations. From my understanding, it seems that Big O ...
2
votes
2answers
236 views

How to deal with questions having two or more asymptotic notations

The following was asked as part of a homework assignment and I am not asking for the solution to these but rather tips or resources on how to solve this and similar questions, Let $f(n)$ and $g(n)$ ...
0
votes
3answers
99 views

Big O relation between $2^n$ and $2^{2n}$

I know that: If $f(n) = O(g(n))$ , then there are constants $M$ and $x_0$ , such that $f(n) <= M*g(n), \forall n > n_0$ The other, plain English way of defining it is, If $f(n)=O(g(n))$ ...
1
vote
1answer
199 views

What is the result of multiplying O(n) and Ω(n)?

If $f(x) = \Omega(n)$ and $g(x)= O(n)$, what would be the order of growth of $f(x) \cdot g(x)$ ? First I figured it should $\Theta(n)$ , as two extremes would cancel each other and the order of ...
2
votes
1answer
72 views

Is there a designation for this not-quite-exponential time?

I've been working and experimenting with an algorithm that may take time $O^*(2^\sqrt{n})$. Here $O^*(f(n))$ simply neglects all polynomial terms. I've seen a comment on Scott Aaronson's blog that ...
1
vote
2answers
111 views

Is $O(N+M)$ exponential or polynomial?

So In a review section, our professor asked: Given integers $N$ and $M$ Is $O(N+M)$ exponential or polynomial. It's exponential, but I just don't see how that is. I would have thought it's linear.
1
vote
0answers
43 views

Big O confusion [duplicate]

I have a question asking about a language L with the property: there is a TM that decides L in time O(n^2013 / (log(n))^2012), and if there is a TM that decides L in time O(n^2012.9). My confusion ...
5
votes
2answers
113 views

Is $\log{n}$ bounded from above by $n^{o(1)}$?

Let $O(n)$ be "Big-O" of $n$ and $o(n)$ be "Small-O" of $n$. It is a well-known fact that $O(n \log{n}) \subset O(n^{1 + \epsilon})$ for any $\epsilon > 0$. Can we omit the $\epsilon$, and just ...
9
votes
2answers
154 views

How to discuss coefficients in big-O notation

What notation is used to discuss the coefficients of functions in big-O notation? I have two functions: $f(x) = 7x^2 + 4x +2$ $g(x) = 3x^2 + 5x +4$ Obviously, both functions are $O(x^2)$, indeed ...
1
vote
1answer
165 views

Polynomial delay

I am reading a paper and it uses the expression "polynomial delay" which I don't understand. It is used in conjonction with the big O notation, which I'm familiar with. Here is a exemple sentence ...
2
votes
4answers
239 views

Why is it O(1) (and not, say, O(2))?

If the running time of an algorithm scales linearly with the size of its input, we say it has $O(N)$ complexity, where we understand N to represent input size. If ...
2
votes
1answer
215 views

Is $\Theta$ symmetric?

For example if $$ f(x)= \Theta (g(x)) $$ from the definition of the theta notation, there exist c1 and c2 constants such that $$c_1 g(x) \le f(x) \le c_2 g(x)$$ then if only we took the constants ...
1
vote
1answer
260 views

Confusion regarding several time complexities including the logarithm

I am new to Advanced Algorithms and I have studied various samples on Google and StackExchange. What I understand is: We use $O(\log n)$ complexity when there is division of any $n$ number on each ...
1
vote
1answer
100 views

In the “tall cache assumption” what does $\Omega$ represent?

Within the field of cache-oblivious algorithms the ideal cache model is used for determining the cache complexity of an algorithm. One of the assumptions of the ideal cache model is that it models a ...
5
votes
1answer
510 views

Variations of Omega and Omega infinity

Some authors define $\Omega$ in a slightly different way: let’s use $ \overset{\infty}{\Omega}$ (read “omega infinity”) for this alternative definition. We say that $f(n) = ...
3
votes
1answer
270 views

Time complexity based on two variables

Suppose we have a function based on two inputs of length $m,n$. Therefore the time complexity of the function is calculated by $T(m,n)$. Suppose that we have: $T(m,c)\in O(m^2)$ for any constant ...
4
votes
2answers
403 views

Asymptotic Properties of Functions in Complexity Analysis

When dealing with the analysis of time and space complexity of algorithms, is it safe to assume that any function which has tight bounds ( i.e. $f(n)=\Theta(g(n))$ is asymptotically positive and ...
0
votes
1answer
56 views

Show that a function belongs to grade of incline [duplicate]

This is a Data structures & Algorithms question. For instance I have the following grades of functions: $O(1), O(2^n), O(n \log n), O(e^n), O(n^3), O(n^{1/3})$ and $O(\log \log n)$ I need to ...
11
votes
2answers
728 views

Construct two functions $f$ and $g$ satisfying $f \ne O(g), g \ne O(f)$

Construct two functions $ f,g: R^+ → R^+ $ satisfying: $f, g$ are continuous; $f, g$ are monotonically increasing; $f \ne O(g)$ and $g \ne O(f)$.
4
votes
2answers
126 views

Landau Notation, Definitions: Limits vs. Corman's

When dealing with Landau notation, $\Theta, O,\Omega,o,\omega$, why do some texts choose the Corman style definitions, i.e.: $$o(g(n))=\{ f(n): \forall c>0:\exists n_0>0:\; 0\leq f(n) < ...