Questions tagged [landau-notation]

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

Filter by
Sorted by
Tagged with
4
votes
5answers
406 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 ...
4
votes
1answer
2k 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
361 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
2answers
553 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 "...
7
votes
2answers
2k 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) = \overset{\infty}{\Omega}(g(...
4
votes
1answer
3k 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 $c$. ...
4
votes
2answers
2k 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
63 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 ...
19
votes
2answers
4k 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)$.
6
votes
2answers
349 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) < cg(n)...
3
votes
2answers
2k views

Methods for Finding Asymptotic Lower Bounds

I've found in many exercises where I'm asked to show that $f(n)=\Theta(g(n))$ where the two functions are of the same order of magnitude I have difficulty finding a constant $c$ and a value $n_0$ for ...
10
votes
5answers
8k views

What is an Efficient Algorithm?

From the point of view of asymptotic behavior, what is considered an "efficient" algorithm? What is the standard / reason for drawing the line at that point? Personally, I would think that anything ...
7
votes
2answers
313 views

Are functions in O(n) that are nor in o(n) all in Θ(n)?

One of my lectures makes the following statement: $$( f(n)=O(n) \land f(n)\neq o(n) )\implies f(n)=\Theta(n)$$ Maybe I'm missing something in the definitions, but for example bubble sort is $O(n^2)$ ...
6
votes
2answers
102 views

Is $\{\Theta(f)|f:\mathbb{N}\rightarrow\mathbb{N}\}$ Dedekind-complete?

Let $\Theta$ and $o$ be defined as usual (Landau-notation). For two equivalence classes defined by $\Theta$ we define $$\Theta(f) <_o \Theta(g) :\Leftrightarrow f \in o(g)\qquad.$$ Let $$\mathbb{F}:...
21
votes
7answers
3k views

Justification for neglecting constant factors in Big O

Many a times if the complexities are having constants such as 3n, we neglect this constant and say O(n) and not O(3n). I am unable to understand how can we neglect such three fold change? Some thing ...
5
votes
3answers
282 views

Why is $(\log(n))^{99} = o(n^{\frac{1}{99}})$

I am trying to find out why $(\log(n))^{99} = o(n^{\frac{1}{99}})$. I tried to find the limit as this fraction goes to zero. $$ \lim_{n \to \infty} \frac{ (\log(n))^{99} }{n^{\frac{1}{99}}} $$ But I'...
-1
votes
1answer
134 views

Big O time complexity

I have a question if I have my $k=300$ and my loop is like this : for( int x = 0 ; x<n ; x--){ for(int y=0 ; y<k; y++){ ... } } Is this ...
25
votes
5answers
12k views

Is O(mn) considered “linear” or “quadratic” growth?

If I have some function whose time complexity is O(mn), where m and n are the sizes of its two inputs, would we call its time complexity "linear" (since it's linear in both m and n) or "quadratic" (...
12
votes
2answers
499 views

Infinite chain of big $O's$

First, let me write the definition of big $O$ just to make things explicit. $f(n)\in O(g(n))\iff \exists c, n_0\gt 0$ such that $0\le f(n)\le cg(n), \forall n\ge n_0$ Let's say we have a finite ...
2
votes
1answer
244 views

asymptotic notations with two exponents

I am familiar with asymptotic notations like Big-O ,little-o. But while I am reading some papers people are using the notations like $O(\epsilon^{1/2^d})$, $O(d)^d$ etc. I couldn't understand these ...
1
vote
1answer
80 views

How is this algorithm in these two complexities?

How is an algorithm with complexity $O(n \log n)$ also in $O(n^2)$? I'm not sure exactly what its saying here, I feel it may be something to do with the fact that big-oh is saying less than or equal ...
4
votes
1answer
167 views

What can be said about Θ-classes in m and n if we know that m < n?

A function in $\Theta(m + n^2)$ and $0 < m < n^2$, is in $\Theta(n^2)$. Does a function in $\Theta(m\log n)$ and $0 < m < n^2$, imply that it is $\Theta(n^2\log n)$?
11
votes
1answer
2k views

Asymptotic Analysis for two variables?

How is asymptotic analysis (big o, little o, big theta, big theta etc.) defined for functions with multiple variables? I know that the Wikipedia article has a section on it, but it uses a lot of ...
3
votes
2answers
585 views

If $f(n) = \Theta(g(n))$, do both functions bound each other for all $n$ or only sufficiently large $n$?

The following is an excerpt from CLRS: $\Theta(g(n))= \{ f(n) \mid \text{ $\exists c_1,c_2,n_0>0$ such that $0 \le c_1 g(n) \le f(n) \le c_2g(n)$ for all $n \ge n_0$}\}$. Assuming $n \in \...
8
votes
3answers
2k views

Why is $3^n = 2^{O(n)}$ true?

$3^n = 2^{O(n)}$ is apparently true. I thought that it was false though because $3^n$ grows faster than any exponential function with a base of 2. How is $3^n = 2^{O(n)}$ true?
7
votes
2answers
167 views

Two functions $g(n)$, $G(n)$ such that $g(n) = o(G(n))$ but $g(n+1) \neq o(G(n))$

The title of the question expresses what I'm looking for - this is to help me better understand the prerequisites for the Non-Deterministic Time Hierarchy Theorem For instance, the Arora-Barak book ...
-1
votes
2answers
13k views

What is the time complexity of the following program?

Please help me calculate the time complexity of the following program. int fun (int n) { if (n <= 2) return 1; else return fun(sqrt(n)) + n; } ...
1
vote
1answer
4k views

Solving the big-Oh notation for $T(n) = 2 T(n/2) + O(n)$ [duplicate]

Possible Duplicate: Solving or approximating recurrence relations for sequences of numbers I know that the solution for $T(n) = 2 T(n/2) + O(n)$ is $ T(n) = O(n \log(n))$ But how do you get to ...
3
votes
1answer
320 views

Why is this $f(n) \leq 6n^3 + n^2 \log n \in O(n^3)$ for all $n \geq 1$?

I'm currently studying for an algorithms midterm in about 2 days and am reading from the beginning of the course, and stumbled upon this when I actually looked at the examples. The question equation: ...
2
votes
3answers
503 views

When does $1.00001^n$ exceed $n^{100001}$?

I have been told than $n^{1000001} = O(1.000001^n)$. If that's the case, there must be some value $n$ at which $1.000001^n$ exceeds $n^{1000001}$. However, when I consult Wolfram Alpha, I get a ...
2
votes
2answers
161 views

Prove that $2^{(log(n)^{1/2})}$ is $O(n^a)$

Hopefully this is the right section. I need to prove that $2^{(log(n)^{1/2})}$ is $O(n^a)$. From the basic principle of Big-O notation, I know I need to find two numbers $c$ and $N$ so that $f(n) \le ...
0
votes
1answer
93 views

Finding $c$ and $n_0$ for a big-O bound

A book I am reading demonstrates how $5n^3 + 2n^2 + 22n + 6 = O(n^3)$, which I believe is true. After all, there exists a value $c$ for which $cn^3$ is always greater than $5n^3 + 2n^2 + 22n + 6$ for ...
5
votes
2answers
3k views

Confusion about big-O notation comparison of two functions

On page 16 of this algorithms book, it states: For example, suppose we are choosing between two algorithms for a particular computational task. One takes $f_1(n) = n^2$ steps, while the other takes ...
1
vote
1answer
3k views

Big Omega of $n \log n$

While studying master method at recurrences topic I'm stacked at a point. It is written in the book as: $T(n) = 3T(n/4) + n \log n$, we have $a = 3, b = 4$, $f(n) = n \log n$, and $...
5
votes
3answers
535 views

How to prove $(n+1)! = O(2^{(2^n)})$

I am trying to prove $(n+1)! = O(2^{(2^n)})$. I am trying to use L'Hospital rule but I am stuck with infinite derivatives. Can anyone tell me how i can prove this?
6
votes
2answers
431 views

Are $\log_{10}(x)$ and $\log_2(x)$ in the same big-O class of functions?

Are $\log_{10}(x)$ and $\log_{2}(x)$ in the same big-O class of functions? In other words, can one say that $\log_{10}(x)=O(\log x)$ and $\log_{2}(x)=O(\log x)$?
8
votes
4answers
1k views

Nested Big O-notation

Let's say I have a graph $|G|$ with $|E|=O(V^2)$ edges. I want to run BFS on $G$ which has a running time of $O(V+E)$. It feels natural to write that the running time on this graph would be $O(O(V^2)+...
16
votes
2answers
15k views

Why is there the regularity condition in the master theorem?

I have been reading Introduction to Algorithms by Cormen et al. and I'm reading the statement of the Master theorem starting on page 73. In case 3 there is also a regularity condition that needs to be ...
6
votes
1answer
2k views

Subtracting lower-order term to prove subtitution method works

Substation method fails to prove that $T(n)=\Theta(n^2) $ for the recursion $T(n)=4T(n/2) + n^2$, since you end up with $T(n) < cn^2 \leq cn^2 + n^2$. I don't understand how to subtract off lower-...
6
votes
2answers
6k views

Why does heapsort run in $\Theta(n \log n)$ instead of $\Theta(n^2 \log n)$ time?

I am reading section 6.4 on Heapsort algorithm in CLRS, page 160. ...
8
votes
1answer
11k views

Solving $T(n)= 3T(\frac{n}{4}) + n\cdot \lg(n)$ using the master theorem

Introduction to Algorithms, 3rd edition (p.95) has an example of how to solve the recurrence $$\displaystyle T(n)= 3T\left(\frac{n}{4}\right) + n\cdot \log(n)$$ by applying the Master Theorem. I am ...
5
votes
3answers
301 views

Complexity inversely propotional to $n$

Is it possible an algorithm complexity decreases by input size? Simply $O(1/n)$ possible?
20
votes
2answers
8k views

Changing variables in recurrence relations

Currently, I am self-studying Intro to Algorithms (CLRS) and there is one particular method they outline in the book to solve recurrence relations. The following method can be illustrated with this ...
1
vote
3answers
817 views

Value of constants in Big Theta notation

In Big Theta notation used for defining the running time of an algorithm, are the constants $c_1$ and $c_2$ different for every value of $n$? Definition: $\qquad \displaystyle \Theta (g(n)) = \{ f(n)...
14
votes
6answers
23k views

n*log n and n/log n against polynomial running time

I understand that $\Theta(n)$ is faster than $\Theta(n\log n)$ and slower than $\Theta(n/\log n)$. What is difficult for me to understand is how to actually compare $\Theta(n \log n)$ and $\Theta(n/\...
9
votes
3answers
24k views

Big O: Nested For Loop With Dependence

I was given a homework assignment with Big O. I'm stuck with nested for loops that are dependent on the previous loop. Here is a changed up version of my homework question, since I really do want to ...
11
votes
2answers
294 views

Is $O$ contained in $\Theta$?

So I have this question to prove a statement: $O(n)\subset\Theta(n)$... I don't need to know how to prove it, just that in my mind this makes no sense and I think it should rather be that $\Theta(n)\...
5
votes
3answers
438 views

Asymptotic growth rate of $f(n)$ and $f(n+1)$

Let $f : \mathbb{R} \rightarrow \mathbb{R}$ be a continuous positive function, where $f(n)$ is integer for each integer $n$. Prove or disprove whether the following always holds: $\qquad f(n+1) = \...
48
votes
4answers
3k views

What is the meaning of $O(m+n)$?

This is a basic question, but I'm thinking that $O(m+n)$ is the same as $O(\max(m,n))$, since the larger term should dominate as we go to infinity? Also, that would be different from $O(\min(m,n))$. ...
7
votes
1answer
891 views

Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$

Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$. The book from which this example is, falsely claims that $T(n) = O(n)$ by guessing $T(n) \leq cn$ and then arguing $\qquad \...