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.

Filter by
Sorted by
Tagged with
26 votes
2 answers
4k 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 ...
user avatar
  • 391
19 votes
3 answers
5k 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 ...
user avatar
  • 291
12 votes
5 answers
4k 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 ...
user avatar
10 votes
2 answers
4k 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 ...
user avatar
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 ...
user avatar
  • 101
8 votes
1 answer
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 ...
user avatar
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....
user avatar
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(...
user avatar
7 votes
1 answer
449 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!
user avatar
  • 151
5 votes
2 answers
167 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 ...
user avatar
  • 77
5 votes
2 answers
292 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 $...
user avatar
5 votes
2 answers
105 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 ...
user avatar
  • 719
5 votes
1 answer
82 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 ...
user avatar
5 votes
1 answer
100 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 ...
user avatar
  • 163
4 votes
2 answers
258 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 ...
user avatar
4 votes
1 answer
374 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 ...
user avatar
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)$?
user avatar
  • 43
4 votes
1 answer
190 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(\...
user avatar
4 votes
1 answer
1k 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 ...
user avatar
  • 69
3 votes
1 answer
2k 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. $$...
user avatar
3 votes
2 answers
316 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 ...
user avatar
  • 337
3 votes
3 answers
237 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),...
user avatar
  • 97
3 votes
2 answers
214 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 ...
user avatar
3 votes
1 answer
78 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)...
user avatar
  • 153
3 votes
1 answer
170 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 ...
user avatar
  • 133
3 votes
2 answers
268 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 ...
user avatar
  • 33
3 votes
2 answers
76 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 ...
user avatar
3 votes
3 answers
198 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 ...
user avatar
  • 131
3 votes
1 answer
38 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....
user avatar
3 votes
1 answer
213 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)$?
user avatar
3 votes
1 answer
148 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 ...
user avatar
  • 133
3 votes
1 answer
79 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 \...
user avatar
3 votes
0 answers
59 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 ...
user avatar
2 votes
3 answers
180 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 ...
user avatar
2 votes
2 answers
3k 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 ...
user avatar
  • 123
2 votes
3 answers
96 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)}...
user avatar
2 votes
4 answers
115 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 ...
user avatar
  • 23
2 votes
5 answers
2k 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 ...
user avatar
2 votes
2 answers
70 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)})$$
user avatar
2 votes
3 answers
122 views

Is it true that $ 2^{O(3k)} = 2^{O(k)} $?

Is it true that $ 2^{O(3k)} = 2^{O(k)} $? But It should be different from $ O(2^{k}) = 2^{O(k)} $ ? I will be happy for simple explanation. Thanks.
user avatar
  • 63
2 votes
2 answers
142 views

Is $\log(n-1) \in \Omega(\log(n))$?

I saw this question Can I simplify log(n+1) before showing that it is in O(log n)? and wanted to know if a similar situation was also true. Namely, is $\log(n-1) \in \Omega(\log(n))$?
user avatar
2 votes
1 answer
232 views

why quicksort can have a best big o notation of (n log n)

I don't really quite understand why quicksort has a big $O$ notation of $(n \log n)$. I would like some help understanding what exactly $(n \log n)$ is, and then how it applies to quicksort. Also in $(...
user avatar
2 votes
2 answers
1k views

Why is n log n dominated by n log^2 n?

Does the rule of $n ^ a$ dominate $n ^ b$ if $a > b$ apply here as well? My understanding is that $n \log n$ will be dominated by $n \log ^2 n$ because of $\log$ being raised to the power of $2$.
user avatar
2 votes
1 answer
65 views

Show that the union of Θ and o is not O

Show that: $\Theta(n\log n)\cup o(n\log n)\neq O(n\log n)$ I tried to start this in many ways but I don't really know how... intuitively isn't $\Theta \cup o = o$? So that would mean that I would ...
user avatar
  • 177
2 votes
2 answers
641 views

Big-O Notation and Calculus?

I was wondering if there are any calculus relationships implicit in Big-O notation. For example, an algorithm linear according to Big-O notation reduces the size of the problem by a constant amount ...
user avatar
2 votes
1 answer
250 views

Time complexity, Big-O for this function?

def f(n): if n < 100000: return 0; for(int i = 0; i < n*n; i++){ return f(n-1) } What is the time complexity? My answer is $O((...
user avatar
2 votes
3 answers
165 views

Determining Big O of a for loop nested within a while loop

I apologize if this question is a duplicate as i cannot find a similar question in this community forum, please comment the post in which this may be a duplicate of so i can update this post :) Im a ...
user avatar
2 votes
3 answers
241 views

Finding largest elements

I was asked to find write a pseudocode of an algorithm that extracts the Log(N) largest elements in an array and return them in a sorted list, my attempt is ...
user avatar
2 votes
2 answers
227 views

How does f(n) < cg(n) specify time?

I have been reading this tutorial on time complexity, and I am a bit puzzled on its explanation of big $O$ notation. It writes: $O(g(n)) = $ { $f(n)$ : there exist positive constants $c$ and $n_0$ ...
user avatar
  • 123
2 votes
2 answers
90 views

Complexity of $O(\log(n^n))$ vs $O(\log(n!))$

Is $O(\log(n^n)) < O(\log(n!))$? Is there any good/practical algorithm with this kind of complexity? And also, to check my understanding of algorithmic complexity, are these two $> O(n\log(n))$...
user avatar

1
2 3 4 5 6