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.
66
questions
24
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 ...
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
423 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!
4
votes
1answer
76 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
99 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
74 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
592 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
3answers
177 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
53 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
56 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
1answer
40 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
45 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
2answers
58 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 ...
2
votes
3answers
95 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
1answer
61 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 ...
2
votes
2answers
107 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
188 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
2answers
56 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
1answer
54 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
1answer
19 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
349 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
0answers
33 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
39 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
294 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
1answer
54 views
why is $O(n^2)$ equal to $n^{1.5}$?
I am learning this MIT course, which gives this formula
$$O(n^2) = n^{1.5}$$
is there a table to calculate this? like $O(n^{1.5})$, $O(n^{5})$ ?
what x takes would have O(x) give $c \cdot n$ where ...
1
vote
3answers
91 views
What should I call algorithms with non-linear non-constant time?
I am writing a paper in which I want to refer to a group of algorithms. Some of these algorithms are of complexity O(NlogN), and some of the are more complex (e.g ...
1
vote
1answer
50 views
Why is building a heap $\mathcal O(n)$ and not $\theta(n)$?
From what I see online, all seem to suggest that heapifying takes $\mathcal O (n)$ time, but it seems like it should always takes $\theta(n)$ time, even in the best case. Is something wrong with my ...
1
vote
1answer
179 views
Solving the recurrence relation T(n) = 2T(n/2) + nlog n via summation
I have seen a few examples of using the master theorem on this to obtain O(n*log^2(n)) as an answer. I am trying to solve this by unrolling and solving the summation, but I can't seem to get the same ...
1
vote
1answer
34 views
Complexity analysis using big - O, Omega and Theta notation
I was reading a research paper and there I read the following:
$t=O\left(d^{2} \log _{d}^{2} n\right)$ matches the lower bound $\Omega\left(d^{2} \log _{d} n\right)$ in the regime where $d=\Theta\...
1
vote
2answers
35 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)...
1
vote
1answer
43 views
About Big O properties
Suppose I have something like the following:
$f(x) = g(x) + O(x^n)$
And I apply a power $m$ to both sides
$f(x)^m = g(x)^m + \cdots + O(x^n)^m$
My question is whether the following is well ...
1
vote
1answer
38 views
Is log(n) equivalent to (log(n))^x for big-O analysis?
My professor noted that we could treat any logarithmic function with an exponent as equivalent to log(n) for the purposes of big-O analysis.
ie. $(n log(n) + 1)^2 + (log(n) + 1)(n^2 + 1)$
From the ...
1
vote
1answer
28 views
Comparing different asymptotic notations
Suppose we have 3 algorithms complexity times at the worst case:
A = $O(nlogn)$
B = $O(n\sqrt{n})$
C = $\Theta(n)$
In my opinion, it is not possible to define the best solution, since we don't know ...
1
vote
0answers
35 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.
1
vote
1answer
50 views
How to prove the performance, Big Omega ,of building a binary heap using recursive method is Ω(nlog(n))
We can learn the big-O of building a binary heap using recursive method is O(n log n) from wiki
"This approach, called Williams’ method after the inventor of binary heaps, is easily seen to run in O(n ...
1
vote
1answer
31 views
Asymptotic notation and random variables
I have two random variables $X$ and $Y$ and I want to bound the value of one in terms of the other (for now, I don't care about the actual distribution of their values).
Suppose that the two ...
0
votes
3answers
79 views
How can i prove this asymptotic comparison? [duplicate]
This is an exercise that's part of my assignment, but it is optional and flagged as a "challenge". I would like to discuss its solution:
Prove that: $$ 27\log{n} + \sqrt{n} = \theta(\sqrt{n})$$
...
0
votes
2answers
74 views
Time-complexity for basic multiplication and division algorithms
The algorithms below has been taken from Discrete Mathematics and it's Applications 7th edition book by Rosen.
p.253 says that "number of shifts required is $O(n^2)$" and "a total of $O(n^2)$ ...
0
votes
1answer
30 views
How does $n^c \lg n, 0<c<1$ compare to other common time complexities
Between what two common time complexities would you place $n^c lg n, 0<c<1$?
The following table illustrates the common time complexities.
Source: wikipedia
0
votes
1answer
46 views
Simplifying this expression with big O when several variables are involved
I have an algorithm which depends on three variables an where the running time is in $\mathcal{O}(m+2 m\cdot n\cdot p+p\cdot(n+m))$ and I would like to simplified it. I proceeded as follows :
\begin{...
0
votes
1answer
46 views
Derive a while loop (which seemingly have some logarithmic traits) runs in $\Theta(n)$
I know for a fact that algorithm A runs in $\Theta(n)$, but how does one derive that?
Algorithm A
...
0
votes
3answers
159 views
How to prove that ($56n^2+106n+48)(\log(264n^2+200)) = Θ(𝑛^2\log n)$
I understand that essentially we have to prove that
$$c_1(n^2\log n)\le
(56n^2+106n+48)(\log(264n^2+200))
\le c_2(n^2\log n)\,.$$
I am confused on how to simplify this further? And ...
0
votes
1answer
44 views
Helping prove this notation for Big-O(n!)
Hello, I was wondering if anyone can help me prove the right part of this double equation. I know the left one is possible due tolog(n!) = Θ(nlogn). Any help is ...
0
votes
2answers
83 views
How to find i-th root of n whose remainder is the smallest?
Given a number n, what is the most assymptotically fast algorithm to express it in terms of base^exponent + rem such that rem is the smallest possible and base is limited from 2 to some relatively ...
0
votes
2answers
112 views
Runtime complexity of a brute force factoring algorithm? (in terms of bits)
Let N be an n bit number. A brute force algorithm factors N by trying to divide N by all of the numbers between 2 and sqrt(N). Given that dividng two n bit integers takes O(n^2) time, what is the ...
0
votes
2answers
421 views
How to find the big o running time if the recursion function have different cases of recursion with different fraction of n?
How to find the big o running time if the recursion function have different cases of recursion with different fraction of n?
If I have a recursive function like this for example (This is just an ...
0
votes
0answers
24 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 ...
0
votes
0answers
35 views
Summing big-O-notation
prove or disprove
$$\text{If } f(n)=g(n)+h(n), \text{ then } O(f(n)) = O(g(n))+O(h(n)).$$
I have no idea about where to begin.
what are the theories which should be used here?
