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.

Filter by
Sorted by
Tagged with
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 ...
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
424 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
77 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
103 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
75 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
190 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
54 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
65 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
132 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
44 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
47 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
99 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
68 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
145 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
202 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
59 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
61 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
89 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
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
408 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
104 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
34 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
44 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
413 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
58 views

Time complexity of $O(n)$ loop which has a multiplication ($O(n^2)$) in it

Assume we know that the implementation for the multiplication operator for a language is known to be $O(n^2)$. Given this pseudocode: ...
1
vote
1answer
55 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
97 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
51 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
461 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
38 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
49 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
59 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
33 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
2answers
490 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 ...
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
32 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
2answers
72 views

Is this program O(n^2logn) or O(nlog^2(n))?

I was wondering whether this program (I'm using a C syntax, hope it's not an issue) is to be considered $O(n^2 \log(n))$ or $O(n\log^2(n))$ or something else entirely. ...
0
votes
2answers
116 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
3answers
93 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
1answer
15 views

Asymptotic growth of a function containing a sum

How to compare the asymptotic growth of a function containing a sum with another function? I'm not sure how I'm supposed to dissolve the sum. Usually I just take the limis of f(x)/g(x). If that fails ...
0
votes
1answer
26 views

Big-O Notation: Runtime Analysis

I have a problem with an exercise, I have to analyze the following For-Loops Then I have to write down the explicit notation, my problem is that I don't know how to get the right m. I tried this but ...
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
48 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{...