# 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.

176 questions
Filter by
Sorted by
Tagged with
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 ...
2k 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 ...
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 ...
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 ...
1k 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....
442 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!
85 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 ...
60 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 ...
89 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 ...
122 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$...
78 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)$?
121 views

58 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)... 1answer 145 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 ... 2answers 66 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 ... 3answers 173 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 ... 1answer 151 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)$? 1answer 76 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 ... 1answer 51 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 \... 0answers 39 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 ... 3answers 102 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 ... 2answers 2k 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 ... 4answers 110 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 ... 5answers 345 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 ... 2answers 453 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. 1answer 59 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 ... 2answers 365 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 ... 1answer 135 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((... 2answers 93 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 ... 2answers 71 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))... 2answers 77 views ### How to determine time complexity with a simple way? I'm learning about time complexity but all the cases we did in class were rather simple. Now I'm working on my home work and the cases our teacher let us have was:$$f(n) = 4n(n + 2 \log^2 n^2) + e^{−... 2answers 37 views ### What does “bounded above” mean in Family of Bachmann–Landau notations? Per wiki |f| is bounded above by g (up to constant factor) asymptotically with this concrete example, $$f(n) = \log n$$ $$g(n) = n^c = n^{0.000001}$$ Does "bounded above (up to constant factor)... 1answer 43 views ### Is it true that$f(n) = c\cdot g(n) + O(g(n))$implies$f(n) = O(g(n))$? Is this true for all$n$and some$c>0$? I'm thinking the answer is yes, but I'm not sure. My thinking is as follows:$f(n) = c\cdot g(n)$for all$n$and some$c>0$is the definition of Big-Oh. ... 1answer 28 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.... 3answers 70 views ### Little O notation relationship Given the functions$𝑓(𝑛)=𝑛^{n}$and$𝑔(𝑛)=10^{10n}$, I am trying to establish the following relationship:$𝑓(𝑛)\notin o(𝑔(𝑛))$. I know to show for the opposite,$𝑓(𝑛)\in o(𝑔(𝑛))$, I ... 1answer 106 views ### Is$(n^5 + n^7)\in \Omega(n^7)$? Shouldn't it be in$\Omega(n^5)$? Is$(n^5 + n^7)\in \Omega(n^7)$? Shouldn't it be in$\Omega(n^5)$? I understand Omega to be a "lower bound" on a function. Shouldn't the largest lower bound on the function$n^5 + n^7$be$n^5$? (... 1answer 24 views ### Asymptotic Relationship from Limit F(n) = n-100 G(n) = n-200 I am trying to show the asymptotic relationship between these two functions using limits. I take the limit n->∞ f(n) / g(n) and I get the result 1 which is constant c. ... 2answers 984 views ### Traveling Salesman Problem: Big O Complexity of Algorithm I'm trying to figure out how to do this problem in my intro algorithm class, but I'm a little confused. The Traveling Salesman problem (TSP) is famous. Given a list of cities and the distances ... 1answer 47 views ### Big O and Little O If$a_n = O(n^\alpha)$and$b_n = o(n^\beta)$, prove that$a_nb_n = o(n^{(\alpha + \beta)})$and$a_n+b_n = O(\max(n^\alpha, n^\beta))$. For the part about$a_nb_n = o(n^{(\alpha + \beta)})$, I get ... 2answers 77 views ### How to determine if given “complex” time complexity is$O(n^2)$? If a given time complexity, such as these:$(n + \log n) * \sqrt{n+\log n}n * (200 + \log^2 n)(7+n^3)\log(n^5)$is not determinable by just looking at it whether is it in class$O(n^2)$or not,... 1answer 56 views ### Is there an algorithm to determine which face of an n-dimensional hypercube is closest to a given point in$O(n\log(n))$? Given a point in N-dimensional space, I'd like to be able to determine which face of an N-dimensional hypercube of edge length 1 that the point is closest to. In the 2-dimensional case it's fairly ... 1answer 39 views ### “Unrolling” a recurrence relation int function(int n) { int i; if (n <= 0) { return 0; } else { i = random(n - 1); return function(i) + function(n - 1 - i); } } ... 1answer 118 views ### How to compare n number of m-dimensional points among one another with minimum time complexity? Suppose there are four points (n = 4) which are four dimensional (m = 4) . Lets say these points are : A(4,1,1,1) , B(3,2,1,1) , C(2,3,3,3) , D(1,4,4,4). What is the best data structure to compare all ... 0answers 36 views ### Which function grows faster: N Log N or N^(1+ε/√(log N)) [duplicate] How would you go about solving this problem? I thought about using a limit infinity approach, but got confused and Wolfram Alpha didn't provide any explanation. 0answers 36 views ### Difference Between$n^{\Omega{(1)}}$and$\Omega{(n)}$[closed] I am not sure about the difference between$n^{\Omega(1)}$and$\Omega(n)$. It seems to me that the only difference is that$n^{\Omega(1)}$can contain some sublinear functions, i.e.,$n^{\frac{1}{2}}\$...
How can we solve summation of asymptotic notations like given below: $$\sum_{k=1}^{n-1} O(n).$$