Questions tagged [big-o-notation]
Big O Notation is an informal name of the "O(x)" notation used to describe asymptotic behaviour of functions. It is a special case of Landau notation, where the O is the Greek letter capital omicron. Please consider using the [landau-notation] tag instead if your question is related to small omicron, omega, or theta in Landau notation.
370
questions
41
votes
4
answers
11k
views
What is the name the class of functions described by O(n log n)?
In "Big O", common notations have common names (instead of saying, "Oh of some constant factor"):
O(1) is "Constant"
O(log n) is "Logarithmic"
O(n) is "Linear"
O(n^2) is "Quadratic"
O(n * log n) ...
- 545
27
votes
2
answers
5k
views
Understanding of big-O massively improved when I began thinking of orders as sets. How to apply the same approach to big-Theta?
Today I revisited the topic of runtime complexity orders – big-O and big-$\Theta$. I finally fully understood what the formal definition of big-O meant but more importantly I realised that big-O ...
- 411
20
votes
3
answers
8k
views
Time complexity $O(m+n)$ Vs $O(n)$
Consider this algorithm iterating over $2$ arrays $(A$ and $B)$
size of $ A = n$
size of $ B = m$
Please note that $m \leq n$
The algorithm is as follows
...
- 301
12
votes
5
answers
6k
views
Does it make sense to say Big Theta of 1? Or should we just use Big O?
Does saying $f(x) = \Theta(1)$ provide any extra information over saying $f(x) = O(1)$?
Intuitively, nothing grows more slowly than a constant, so there should be no extra information in specifying ...
- 249
11
votes
3
answers
3k
views
Is Big-Theta a more accurate description of worst case run time than Big-O?
Question I was asked: Does it make a difference if I say "The worst case run time is $O(n^2)$ vs the worst case run time is $\Theta(n^2)$?"
To me, the only difference is that when we say $O(...
10
votes
2
answers
3k
views
Are there any functions with Big O (Busy Beaver(n))?
So, I was reading this article by Scott Aaronson on big numbers, and he mentioned that the Busy Beaver sequence increases faster than all sequences computable by Turing Machines. Faster than ...
- 231
10
votes
2
answers
6k
views
Can I multiply Big-O time complexities?
Can I multiply Big-O time complexities?
For example: $O(n) \cdot O(n) = O(n^2)$?
UPDATE:
The question came from my observation that different sources analyze their algorithms in different ways. For ...
- 211
9
votes
6
answers
3k
views
Are there variations of the regular runtimes of the Big-O-Notation?
There are multiple $O$-Notations, like $O(n)$ or $O(n^2)$ and so on. I was wondering, if there are variations of those in reality such as $O(2n^2)$ or $O(\log n^2)$, or if those are mathematically ...
- 101
8
votes
2
answers
2k
views
Isn't linear time O(n)?
In the question in this video about quicksort luckily picking the median in each recursive call. Tim Roughgarden, the presenter, says at 11:22
Partition needs really linear time, not just $O(n)$ time....
- 659
7
votes
3
answers
3k
views
What are you allowed to move into the big O notation for it to be still correct?
Can someone tell me what the rules are for moving log or exponents into the $O(n)$ notation so it is still correct?
For example: Is this $\log(O(n))= O(\log(n))$ correct? Or is this correct $O(n)^2=O(...
- 73
7
votes
1
answer
455
views
Asymptotics question
Is $\frac {n!} {2!\cdot 4!\cdot 8!\dots (n/2)!}=O(4^n)$?
I am really stuck and I tend to believe it's true, but I don't know how to prove it.
Any help would be appreciated!
- 231
7
votes
1
answer
599
views
Possible Mistake in Skiena's Algorithm Design Manual
In Skiena's book Algorithm Design Manual, 3rd Edition, it is claimed on page 45 that
$$
mn - m^2 + m \in \Omega(mn)
$$
where $m,n \geq 0$ and $m \leq n$. I claim that this is in fact false, with the ...
- 173
6
votes
2
answers
326
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
5
votes
5
answers
4k
views
Time Complexity of Linear Search vs Brute Force
I am currently watching the FreeCodeCamp Algorithms and Data Structures Tutorial. In the explanation for exponential time complexity, they explain that using a brute force attack on a combination lock ...
5
votes
2
answers
211
views
How does $Θ(\log(n!))=Θ(\log(n^n)$?
How does $Θ(\log(n!))=Θ(\log(n^n)$?
I understand why $Θ(\log(n!))=Θ(n\log(n))$ and $Θ(\log(n^n))=Θ(n\log(n))$, therefore $Θ(\log(n!))=Θ(\log(n^n)$. But I am having trouble reconciling this with the ...
- 77
5
votes
2
answers
444
views
Upper bounds for a binomial coefficient
I have an algorithm with worst-case time complexity in $\mathcal O (\binom{k}{p-1})$, where $k$ is a parameter and $p$ is the input size of that algorithm. I further have determined that $p-1 \leq k $...
5
votes
2
answers
115
views
Why $\frac{n^3}{2^{\Omega(\sqrt{\log n})}}$ doesn't refute the lower bound $O(n^{3-\delta})$?
I have a simple quesiton:
It is conjectured that All Pairs Shortest Path (APSP) has no $O(n^{3-\delta)}$-time algorithm for any $\delta >0$ by SETH.
also
there is a result that says APSP can ...
- 749
5
votes
1
answer
116
views
Does big-Oh impose an ordered partition on the set of the "usual" functions?
The example in this answer proves the fact familiar to CS students - that the "big-O" is not a total order. However, most algorithm running times analyzed using big-Oh notation are not ...
- 258
5
votes
1
answer
123
views
Exact meaning of $2^{\mathcal{O}(f(n))}$
In Sipser's Introduction to the Theory of Computation he uses the notation $2^{\mathcal{O}(f(n))}$ to denote some asymptotic running time.
For example he says that the running time of a single-tape ...
- 163
4
votes
2
answers
106
views
How to Determining the Big O Complexity of a Recursive Function?
I'm struggling to determine the correct time complexity of a recursive function from an exam question. The function definition is as follows:
fun (n) {
...
- 43
4
votes
2
answers
541
views
How does knowing the input size make the time complexity of a function constant?
After reading the question and answers on Time complexity of min() and max()? I would like to clear up some confusion on the relation between time complexity and size of input.
First, I've noticed ...
- 173
4
votes
1
answer
764
views
Big O vs. Big Theta for AVL tree operations
On the Wikipedia page for AVL trees, the time/space complexity for common operations is stated both for average case (in Big Theta) and worst case (in Big O) scenarios. I understand both Big O and Big ...
- 43
4
votes
1
answer
80
views
Asymptotics of $\frac{1}{\log(\frac{2^n}{2^n-1})}$
I am trying to understand the asymptotics of
\begin{equation}
f(n) = \frac{1}{\log(\frac{2^n}{2^n-1})}
\end{equation}
In particular, is there some $c \geq 1$ such that $f(n) = O(n^c)$?
- 43
4
votes
1
answer
251
views
Improving time complexity from O(log n/loglog n) to O((log ((nloglog n)/log n))/loglog ((nloglog n)/log n))
Suppose I have an algorithm whose running time is
$O(f(n))$ where $f(n) = O\left(\frac{\log n}{\log\log n}\right)$
And suppose I can change this running time in $O(1)$ steps into $O\left(f\left(\...
- 157
4
votes
1
answer
2k
views
What does $|V|=O(|E|)$ mean?
I was reading about Dijkstra's algorithm from this Stanford University lecture presentation. On page 18 it says Dijkstra's algorithm is $O(|V|\log|V|+|E|\log|V|)$ and I understand why. But then it ...
- 69
3
votes
1
answer
3k
views
Arrange in increasing order of asymptotic complexity
I have the following functions that I need to rank in increasing order of Big-O complexity:
$$(\log n)^3, 10\sqrt n, n\log n, n\sqrt n, n^4 + n^3, (2.1)^n \cdot n^2, 3^n, 2^n \cdot n^3, n! + n, n^n. $$...
- 147
3
votes
2
answers
608
views
Asymptotic Analysis of T(n) = 2T(n/8) + 2T(n/4) + n
Given the recurrence
$$T(n) = 2T\bigg(\frac{n}{8}\bigg) + 2T\bigg(\frac{n}{4}\bigg) + n$$
My professor says that $T(n)$ is $O(n\log n)$ but I have calculated a complexity of $O(n)$ as shown below with ...
- 367
3
votes
3
answers
304
views
Find the error in the following “proof” that $O(n) = O(n^2)$
Let $f(n) = n^2 , g(n) = n$, and $h(n) = g(n)−f(n)$. It is clear that $h(n) ≤ g(n) ≤ f(n)$ for all $n ≥ 0$. Therefore, $f (n) = \max(f (n), h(n))$. Thus,
$O(n) = O(g(n)) = O(f(n) + h(n)) = O(\max(f(n),...
- 107
3
votes
2
answers
216
views
What would be the big O notation for a function that attempts to find pairs of users that participate in different discussions?
Recently, I started to think of a problem involving the use of Twitter data that would involve finding pairs of users that participate in the most conversations. For example, with each tweet, you get ...
3
votes
1
answer
85
views
How to calculate Big O of $T(n) = aT(n^b) + f(n)$?
I'm a student studying Big O. I know that we can solve $T(n) = aT(\frac{n}{b}) + f(n)$ by compering $n^{\log_b{a}}$ to $f(n)$ or
$O(n^{\log_b{a}} + f(n))$
Today I was faced with $T(n) = T(\sqrt n)...
- 153
3
votes
1
answer
174
views
Shifted Big Os. How to say O((n+c)!) = O(n!)?
Suppose an algorithm is $O(n!)$, but we need to run it $n$ times, so the total complexity is
$nO(n!) = O(n \cdot n!) = O((n+1)! - n!) = O((n+1)!)$
Strictly, there is no constant factor that would make ...
- 133
3
votes
2
answers
369
views
Comparing asymptotic running time of two algorithms $\sqrt n$ and $2^{\sqrt{\log _{2}n}}$
Given two algorithms with their time-complexity $t_a(n)=\sqrt{n}$ and $t_b(n) = 2^{\sqrt{\log _{2}n}}$ and i have to show $t_b(n) = O(t_a(n)) $.
I´ve made a program to check this statement and it ...
- 33
3
votes
2
answers
85
views
Struggling to understand the symbolism around the big oh formal definition
I'm struggling to understand what exactly T(n), and f(n) is in the above text:
When we compute the time complexity T(n) of an ...
- 141
3
votes
3
answers
211
views
What is the complexity of $i^i$?
What is the complexity of the following algorithm in Big O:
for(int i = 2; i < n; i = i^i)
{
...do somthing
}
I'm not sure if there is a valid operator to ...
- 131
3
votes
1
answer
41
views
Order notation subtractions in Fibonacci Heap
Can order notation on its own imply:
$O(D(n)) + O(t(H)) - t(H) = O(D(n))$
My guess is that you cannot since the constant in the O(t(H)) would still exist after the subtraction if the constant is > 0....
- 205
3
votes
1
answer
481
views
Is O(n log n) exponential speedup over O(n^2)?
I would like to know if $O(n \log n)$ is an exponential speedup over $O(n^2)$?
- 33
3
votes
1
answer
199
views
Combining Predicate Logic and BigO
I am a beginner to predicate logic and BigO and am having though time understanding the definition of BigO in terms of predicate logic in the picture attached. I particularly am unable to understand ...
- 133
3
votes
1
answer
100
views
Compare log^k(n) with n^(1/2)
I'm trying to prove or disprove that $\log^{k}(n) \in O(\sqrt{n}), \ \forall k > 0$. By using the free version of wolfram and testing some increasing values of $k$ I get that:
$$\lim_{n \...
- 253
3
votes
0
answers
86
views
What's the fastest known non-galactic algorithm for matrix multiplication of large matrices
"A galactic algorithm is one that outperforms any other algorithm for problems that are sufficiently large, but where "sufficiently large" is so big that the algorithm is never used in ...
- 356
3
votes
0
answers
106
views
Induction pitfalls with O notation and recursion
I read the following in CLRS 3rd Ed:
I'm not sure I understand exactly how to avoid this pitfall.
How would one know that the $\mathcal{O}$ notation in this case grows with $n$ and is thus not ...
2
votes
3
answers
339
views
How can $\Theta$ and $O$ complexities be different?
From the definition of the $\Theta$-notation,
$$f(n)=\Theta(g(n))\\\implies \exists n_0, \exists c_1,c_2\gt 0, \forall n\gt n_0, c_1\cdot g(n)\le f(n)\le c_2\cdot g(n)$$
We can see that the ...
- 123
2
votes
3
answers
147
views
How to simplify $O(\log (n!))$?
I have a problem with this time complexity: $\log (n!)+\frac{5}{2}n\log\log n$. I'm not sure how to deal with the $n!$ term. I know from calculus class that the sequence $n!$ is bigger than any ...
- 31
2
votes
2
answers
5k
views
Are "of the order of n" and "Big O" the same thing?
I am learning from the MIT course Introduction to Algorithms.
The professor says:
Now, remember $\Theta(n)$ is essentially something
that says "of the order of $n$".
What does "of the order ...
- 123
2
votes
3
answers
103
views
$\log_{2}{(\frac{1}{2}n)} + \log_{2}{(\frac{1}{4}n}) + \log_{2}{(\frac{1}{8}n)} + \ldots + \log_{2}{(\frac{1}{2^{log_{2}(n)}}n)} = O(\log_{2}(n))$?
I am trying to analyze a series that I found, in the analysis of an algorithm. And I was wondering if the following was true:
$$\log_{2}{\left(\frac{1}{2}n\right)} + \log_{2}{\left(\frac{1}{4}n\right)}...
- 169
2
votes
3
answers
100
views
$f(n)=n^{100}$, $g(n)=2^{n/100}$, determine whether $f=O(g)$
I am reading Arora and Barak's book "Computational Complexity: A Modern Approach". I am doing EXERCISE 0.1.(b): $f(n) = n^{100}$, $g(n)=2^{n/100}$, determine whether $f=O(g)$.
Here's what I ...
- 243
2
votes
4
answers
123
views
Is this big O notation format correct? $3^n = 2^{(O(n))}$
I am completing a university exercise deciding whether big notations are true or false.
I am stuck on this question :
$$3^n = 2^{(O(n))}$$
I want to answer False as the format looks incorrect and ...
- 23
2
votes
5
answers
3k
views
Big O notation for Average case in Linear search
Average case complexity for linear search is (n+1)/2 i.e, half the size of input n.
The average case efficiency of an algorithm can be obtained by finding the average number of comparisons as given ...
2
votes
2
answers
185
views
2
votes
2
answers
316
views
Does $f(n) \in O(g(n))$ imply $2^{f(n)} \in O(2^{g(n)})$?
Is the following true: $$ f(n) \in O(g(n)) \text{ then } 2 ^ {f(n)} \in O(2^{g(n)})$$
- 23
2
votes
3
answers
357
views
Silly question: what counts as a "unit of work" when computing big-Oh time complexity
I am going through a fairly non-rigorous textbook called 'Cracking the code interview' and I am bothered by this terminology called "unit of work".
It says in the textbook that certain ...
- 121