Questions tagged [landau-notation]

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

252 questions
Filter by
Sorted by
Tagged with
25k 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 ...
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)$ ...
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 ...
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))$. ...
10k views

8k 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 ...
287 views

Is O((n^2)*log(n)) greater than O(n^(2.5))?

I know that $O(n^2\times \log(n))$ is greater than $O(n^2)$, but is $O(n^2\times \log(n))$ greater than $O(n^{2.5})$?
470 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 ...
491 views

6k 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 ...
1k 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 ...
639 views

605 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 ...
5k 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. ...
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?