Skip to main content

# 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
Filter by
Sorted by
Tagged with
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

• 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 ...
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 ...
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) { ...
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 $$f(n) = \frac{1}{\log(\frac{2^n}{2^n-1})}$$ In particular, is there some $c \geq 1$ such that $f(n) = O(n^c)$?
• 43
4 votes
1 answer
251 views

• 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

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 ... 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)$? 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 ... 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 ... 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 ### What is the Time Complexity of this Slow Sorting Algorithm? ... • 59 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)})$$
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