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.
153
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 ...
7
votes
1answer
441 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
82 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
59 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
88 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
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
115 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
629 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
546 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
209 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
55 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
120 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
164 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
146 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
57 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
50 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
35 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
101 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
198 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
305 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
2answers
354 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
55 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
1answer
104 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
89 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
68 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
74 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
41 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
66 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
102 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
23 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
782 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
2answers
74 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
51 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
34 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
116 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
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
144 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 ...
1
vote
2answers
54 views
What is the big-$O$ notation of a summation of a log?
For:
$$\sum^{n+m}_{i=n} \log(i)$$
I'm wondering what the big O notation is and how to prove it...
I believe that we can also write this as
$$\log(n) + \log(n+1) + \log(n + 2) + \ldots + \log(n+m)$$
...
1
vote
1answer
79 views
How do I simplify $O\left({n^2}/{\log{\frac{n(n+1)}{2}}}\right)$
I'm not very certain about how to deal with asymptotics when they are in the denominator. For $$O\left(\frac{n^2}{\log{\frac{n(n+1)}{2}}}\right)$$, my intuition tells me that it should be treated in a ...
1
vote
2answers
144 views
1
vote
1answer
51 views
Solving a multivariate equation for asymptotic complexity
I have a function $f(m, n)$ with time complexity $T(m, n)$ characterized by the recurrence relation
$$\begin{align}
T(m,\ n) &= 2T\bigl(\frac{m}{2}, \frac{n}{2}\bigr) + c_0 \log n + c_1.\\
T(m,\ ...
1
vote
2answers
32 views
Time complexity of Vertex Cover vs Clique for fixed k
I have 2 ways of solving Independent Set problem of fixed size $k$ for graph $G = (V, E)$:
- Vertex Cover algorithm running in $O^*(1.47^{V - k})$ (optimized recursive algorithm)
- Clique algorithm ...
