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
25
votes
2answers
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 ...
12
votes
5answers
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 ...
9
votes
6answers
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 ...
8
votes
1answer
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 ...
8
votes
2answers
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....
7
votes
1answer
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!
5
votes
2answers
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 ...
5
votes
1answer
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 ...
5
votes
1answer
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 ...
4
votes
2answers
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 $...
4
votes
1answer
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)$?
4
votes
1answer
121 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(\...
4
votes
1answer
667 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 ...
3
votes
1answer
645 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. $$...
3
votes
3answers
210 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),...
3
votes
1answer
58 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)...
3
votes
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 ...
3
votes
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 ...
3
votes
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 ...
3
votes
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)$?
3
votes
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 ...
3
votes
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 \...
3
votes
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 ...
2
votes
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 ...
2
votes
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 ...
2
votes
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 ...
2
votes
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 ...
2
votes
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$.
2
votes
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 ...
2
votes
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 ...
2
votes
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((...
2
votes
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$ ...
2
votes
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))$...
2
votes
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^{−...
2
votes
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)...
2
votes
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.
...
2
votes
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....
2
votes
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 ...
2
votes
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$? (...
2
votes
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.
...
2
votes
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 ...
2
votes
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 ...
2
votes
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,...
2
votes
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 ...
2
votes
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);
}
}
...
2
votes
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 ...
2
votes
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.
2
votes
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}}$...
1
vote
2answers
195 views
Summation of asymptotic notation
How can we solve summation of asymptotic notations like given below:
$$
\sum_{k=1}^{n-1} O(n).
$$
1
vote
3answers
1k views
Why is heap insert O(logN) instead O(n) when you use an array?
I am studying about the arrays vs heap for make a priority queue
For check the heap implementation I am reviewing this code: Heap
, but I have the following question.
Heap is based on array, and ...
