# Questions tagged [landau-notation]

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

258 questions
Filter by
Sorted by
Tagged with
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 ...
2k views

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$. ...
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 ...
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 ...
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)$.
349 views

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 ...
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'...
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 ...
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" (...
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 ...
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 ...
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 ...
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)$?
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 ...
585 views

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 ...
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 ...
3k views

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

### Complexity inversely propotional to $n$

Is it possible an algorithm complexity decreases by input size? Simply $O(1/n)$ possible?
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 ...
817 views

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 ...
294 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))$. ...
### 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 \...