Questions tagged [landau-notation]
Questions about asymptotic notations such as Big-O, Omega, etc.
57
questions
41
votes
6
answers
20k
views
Sorting functions by asymptotic growth
Assume I have a list of functions, for example
$\qquad n^{\log \log(n)}, 2^n, n!, n^3, n \ln n, \dots$
How do I sort them asymptotically, i.e. after the relation defined by
$\qquad f \leq_O g \...
- 619
101
votes
3
answers
35k
views
How does one know which notation of time complexity analysis to use?
In most introductory algorithm classes, notations like $O$ (Big O) and $\Theta$ are introduced, and a student would typically learn to use one of these to find the time complexity.
However, there are ...
- 1,323
49
votes
4
answers
71k
views
How do O and Ω relate to worst and best case?
Today we discussed in a lecture a very simple algorithm for finding an element in a sorted array using binary search. We were asked to determine its asymptotic complexity for an array of $n$ elements.
...
- 1,045
53
votes
4
answers
7k
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))$. ...
- 1,612
25
votes
7
answers
6k
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 ...
- 1,799
29
votes
5
answers
21k
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" (...
- 1,167
23
votes
2
answers
11k
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 ...
- 331
10
votes
3
answers
1k
views
Sums of Landau terms revisited
I asked a (seed) question about sums of Landau terms before, trying to gauge the dangers of abusing asymptotics notation in arithmetics, with mixed success.
Now, over here our recurrence guru JeffE ...
- 72.4k
14
votes
3
answers
1k
views
What goes wrong with sums of Landau terms?
I wrote
$\qquad \displaystyle \sum\limits_{i=1}^n \frac{1}{i} = \sum\limits_{i=1}^n \cal{O}(1) = \cal{O}(n)$
but my friend says this is wrong. From the TCS cheat sheet I know that the sum is also ...
- 72.4k
48
votes
10
answers
11k
views
O(·) is not a function, so how can a function be equal to it?
I totally understand what big $O$ notation means. My issue is when we say $T(n)=O(f(n))$ , where $T(n)$ is running time of an algorithm on input of size $n$.
I understand semantics of it. But $T(n)$ ...
- 591
20
votes
2
answers
7k
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)$.
- 333
9
votes
2
answers
31k
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 ...
- 461
6
votes
2
answers
1k
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)$?
- 1,607
6
votes
2
answers
312
views
Why is $\sum_{i=1}^n O(i)$ not the same as $O(1)+O(2)+\dots+O(n)$?
The well-known textbook Introduction to Algorithms ("CLRS", 3rd edition, chapter 3.1) claims the following:
$$ \sum_{i=1}^n O(i) $$
is not the same as (I'm not using DNE because the book explicitly ...
Padaca
15
votes
4
answers
710
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 ...
- 253
13
votes
1
answer
3k
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 ...
- 133
11
votes
6
answers
12k
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 ...
- 2,911
9
votes
4
answers
2k
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)+...
- 1,793
8
votes
3
answers
9k
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))$.
...
7
votes
2
answers
462
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)$ ...
- 2,911
1
vote
2
answers
1k
views
Summation of asymptotic notation
How can we solve summation of asymptotic notations like given below:
$$
\sum_{k=1}^{n-1} O(n).
$$
- 11
34
votes
1
answer
20k
views
What does tilde mean, in big-O notation?
I'm reading a paper, and it says in its time complexity description that time complexity is $\tilde{O}(2^{2n})$.
I have searched the internet and wikipedia, but I can't find what this tilde signifies ...
20
votes
1
answer
15k
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 ...
- 423
10
votes
3
answers
791
views
Error in the use of asymptotic notation
I'm trying to understand what is wrong with the following proof of the following recurrence
$$
T(n) = 2\,T\!\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+n
$$
$$
T(n) \leq 2\left(c\left\...
- 373
9
votes
3
answers
32k
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 ...
user1000229
8
votes
2
answers
3k
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(...
- 207
8
votes
2
answers
3k
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 ...
- 131
6
votes
1
answer
949
views
What does the "big O complexity" of a function mean?
What do people mean when they refer to the "big O complexity" of a function? What is the big O complexity of $9n^2 + 10n$, for example?
- 277k
6
votes
2
answers
906
views
Why do Θ-bounds not survive taking differences?
$f_1$, $f_2$, $g_1$, and $g_2$ are functions such that:
$$f_1 = \Theta(f_2)$$
$$g_1 = \Theta(g_2)$$
I was able to prove that:
$$\frac{f_1}{g_1} = \Theta\biggl(\frac{f_2}{g_2}\biggr)$$
But I can't ...
- 315
5
votes
3
answers
665
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?
- 355
5
votes
1
answer
892
views
What is "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 example sentence ...
5
votes
3
answers
316
views
Complexity inversely propotional to $n$
Is it possible an algorithm complexity decreases by input size? Simply $O(1/n)$ possible?
- 153
3
votes
2
answers
3k
views
Is $\log(n!)$ in $\Theta(n \log(n))$?
I had two questions on my automated test which I don't understand the answer for.
$\log(n!) = \log(n\cdot (n-1)\cdot \cdots \cdot 2\cdot 1) = \log(n)+\log(n-1)+....+\log(1)$. So it is in $O(n\log(...
- 400
2
votes
1
answer
228
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 ...
- 882
0
votes
1
answer
4k
views
Asymptotic relationship of logarithms in different bases
I'm reading through the Khan Academy course on algorithms. I'm taking a quiz and finally got the right answer (all 3 of the options are true).
For the functions $\lg n$ and $\log_8 n$, what is the ...
- 103
47
votes
2
answers
7k
views
Order of growth definition from Reynolds & Tymann
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 ...
- 581
19
votes
3
answers
22k
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 ...
GrowinMan
9
votes
1
answer
1k
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 \...
- 919
7
votes
2
answers
7k
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.
...
- 461
7
votes
4
answers
5k
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, ...
- 259
6
votes
1
answer
639
views
What does $n^{O(1)}$ mean?
I read an example that said explain what "$f(n)$ is $n^{O(1)}$" means.
I can't interpret the $n^{O(1)}$ syntax. I know what Big $O$ notation is, its just that this example looks odd to me.
- 261
6
votes
2
answers
112
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}:...
- 2,299
6
votes
2
answers
492
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)...
- 2,911
6
votes
3
answers
1k
views
How did they cancel out O-terms in this fraction?
While reading a book about algorithms, I came across this derivation:
$$
\frac{2a_0(2N) \ln(2N) + O(2N)}{2a_0N\ln N+O(N)} =
\frac{2\ln(2N) + O(1)}{\ln N+O(1)} =
2 + O\left(\frac{1}{\log N}\right).
$$
...
- 249
5
votes
4
answers
4k
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 ...
- 639
4
votes
1
answer
4k
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$.
...
- 143
4
votes
2
answers
426
views
What does the $O^*$ notation mean?
I'm recently reading some papers on the maximum independent set problem, all the algorithms' time complexity is donated by $O^*()$ notation, like $O^*(1.0836^n)$. One paper says "the $O^*$notation ...
- 652
4
votes
2
answers
108
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 function:...
- 1,013
3
votes
1
answer
456
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 ...
- 14.8k
2
votes
3
answers
77
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:
...
- 123