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

247 questions
Filter by
Sorted by
Tagged with
324 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)$$ ...
95 views

### Big theta notation

I'm trying to figure out the following problem: If algorithm $A$ has a big theta notation of $n^3$ and algorithm $B$ has a big theta notation of $n^2$, there might be an infinite number of ...
471 views

### What is the time complexity Big-O of this algorithm?

What is the time complexity Big-O of this algorithm? , The first assumption it's O(N * lg N) but it is not correct, why? ...
124 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 ...
68 views

### Comparing growth of two sums of functions

Does $n+n^4$ grow faster than $n^2+n^3$? If so, why?
99 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 ...
19 views

### Big O notation space/time

I realize that each time I have to deal with the Big-O notation I am questioning myself why complexity in time or space share the same formal notation/letter. It is always confusing when I read ...
95 views

### What does $(\log n) \cdot (\log n)$ simplify to in Big O notation?

Does it simplify to $O(\log n)$ or $O(\log^2 n)$ or something else entirely? I am a bit stuck on this one.
44 views

...
66 views

### Algorithms: Determining Asymptotic Notation from a given execution time

I'm studying for an Algorithms and Data Structure test. There is a type of question that is usually always asked by my professor but I don't know how to answer/solve it. Question 1: An Algorithm with ...
79 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))$...
64 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); } } ...
33 views

### Big O notation of $\left(\begin{array}{c} n\\ \frac{n}{2} \end{array} \right)$

What is the O-notation (or $\Theta$ notation ) of $\left(\begin{array}{c} n\\ \frac{n}{2} \end{array} \right)$ ? Can I use Sterling approximation : $n! = \Theta(\sqrt{n}\left(\frac{n}{e}\right)^n)$ ...
302 views

### Big O of rational function using the definition

I want to prove that $\dfrac{3x^3+2x^2+x+1}{4x^2+1}$ is $O(x)$. I am having problem in finding $c$ and $k$ and proving that it is big O, since the function involves a fraction. How would I go about ...
44 views

3k views

### Time complexity for concatenating strings

I was going through this piece of code from an algorithms books and something doesn't look clear Please ignore the spelling errors, How does 0(x + 2x + nx) reduce to o(xn^2) ? My analogy, assuming ...
104 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 ...
535 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: ...
1k 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. ...
37 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 ...
115 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$? (...
181 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)$?
125 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 ...
226 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 ...
937 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$.
83 views

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