Questions tagged [landau-notation]

Questions about asymptotic notations such as Big-O, Omega, etc.

Filter by
Sorted by
Tagged with
1
vote
2answers
118 views

What kind of growth is $O(0.24\cdot K\cdot 2^w)$

I've calculated the running time of an algorithm I'm interested in to be $$O(0.24\cdot K\cdot 2^{w})\,,$$ where $K$ and $w$ are both variables. ($K$ is the number of elements in some set, ...
1
vote
1answer
123 views

What's the difference between $O(1)$ and $o(1)$?

What's the difference between $O(1)$ and $o(1)$ ?
2
votes
1answer
54 views

Which is better wording: x grows with $N^2$ or x grows with $O(N^2)$

Which of the following sounds better (or more rigorously): x grows with $N^2$ or x grows with $O(N^2)$ or x grows quadratically with $N$.
1
vote
1answer
119 views

Big O - Equivalence: “Standard” definition vs Limit definition

This question is related to: Landau Notation, Definitions: Limits vs. Cormen's. Consider functions $f, \ g : N \rightarrow R^{\geq0}$. For small-$o$, the definition: $$f(n)\in o(g(n)) \iff \forall ...
2
votes
1answer
381 views

Does the transitivity of big-O notation hold for asymptotically nonnegative functions?

I'm reading the book Introduction to Algorithms and in Chapter 3 it is said that if $f(n)$ and $g(n)$ are asymptotically positive then $$ f(n) = O(g(n)) \text{ and } g(n) = O(h(n)) \text{ implies } f(...
5
votes
1answer
168 views

What does $n^{O(1)}$ mean?

I read an example that said explain what "$f(n)$ is $n^{O(1)}$" means. I can't interpret the $n^{O(1)}$ syntax. I know what Big $O$ notation is, its just that this example looks odd to me.
1
vote
2answers
205 views

Disproving using the definition of O

Formally show that $0.1n + 10\sqrt{n}$ is not $O(\sqrt{n})$ using the definition of $O$ only. I cannot find much on how to solve a problem like this, nor do i know how. Am I supposed to show some ...
2
votes
1answer
443 views

$O(n+nm) = O(nm) = O(m+nm)$?

I am thinking about the worst-case space complexity of an algorithm. Obviously, if $f \in O(nm)$ then $f \in O(n+nm)$. But is the converse true? $O(m)+O(nm) = O(m+nm) = O(m(1+n)) = O(m)O(1+n) = O(m)...
-4
votes
1answer
498 views

Equivalent definitions of big O

Let $A = \{ g(n) \mid \exists c,n_0 \, \forall n \ge n_0\colon g(n) \le cf(n) \}$, and $B = \{ g(n) \mid \exists c,n_0 \, \forall n \geq n_0 \colon g(n) < cf(n) \}$. Prove $A = B$. My ...
2
votes
1answer
56 views

Can parameters other than $n$ be always ignored in big $O$ notation?

The Bentley–Ottmann algorithm, for example, has time complexity of $O((n + k) \log n)$. Is the statement $O((n + k) \log n) = O(n \log n)$ true? I know that $k$ is there because it has big ...
0
votes
1answer
291 views

In asymptotic notation how to prove that $\mathcal{O}(g(n))\subseteq\mathcal{O}(f(n))\implies\mathcal{O}(f(n)+g(n))=\mathcal{O}(f(n))$

I have to prove that $$\mathcal{O}(g(n))\subseteq\mathcal{O}(f(n))\implies\mathcal{O}(f(n)+g(n))=\mathcal{O}(f(n))$$ The functions are non-negative. Clarification: $$\mathcal{O}(f(n)+g(n))=\...
1
vote
1answer
974 views

Running time complexity of Binary Search Trees and Big-Omega

I know that the main operations (Insert, Search, Delete) have a worst-case running time of $\mathcal{O} (h)$. But I wanted to dig into this deeper. Basically I am having some difficulties ...
0
votes
1answer
168 views

How to compare computational complexity of algorithms

I have three different algorithms for achieving a target. Algorithm 1 takes $O(Mn)$ - $M$ is constsnt and n is variable,Algorithm 2 takes $O(min(p^3,n^3))$ - both $p$ and $n$ is variable and Algorithm ...
0
votes
1answer
678 views

Asymptotic relationship of logarithms in different bases

I'm reading through the Khan Academy course on algorithms. I'm taking a quiz and finally got the right answer (all 3 of the options are true). For the functions $\lg n$ and $\log_8 n$, what is the ...
0
votes
1answer
183 views

Why is $\log n = O(2^n)$? [duplicate]

In my theoretical computer science book I have the following statement regarding the space complexity of $f(n)=2^n$: $$\log(n) = O(f(n))$$ I can't understand how this is true, any help will be ...
-2
votes
2answers
331 views

Understanding constants in big-O notation

I am having a difficult time understanding big-O notation for the growth of functions. My textbook says the following. Example 2 shows that $7x^2$ is $O(x^3)$. Is it also true that $x^3$ is $O(7x^...
1
vote
2answers
1k views

In algorithm analysis what does it mean for bounds to be “tight”

For example we could say alg(x) runs big omega(n) but this bound is not "tight". What is meant by "tight"? Is it that the bound isn't at its maximum? So maybe a tighter bound could be big omega (1)??...
0
votes
2answers
263 views

How to prove that $n^2$ is not $o(n^2+10^{10}n)$?

I need to prove that $n^2$ is not $o(n^2+10^{10}n)$. I thought of the limit test: $$ \lim_{n \to \infty} \frac{n^2}{n^2+10^{10}n} = 1 \Rightarrow n^2 = \Theta(n^2+10^{10}n) $$ However I'm not sure ...
-1
votes
4answers
255 views

Difference of Big-Oh terms — what is the result?

I'd like to double-check my understanding of Big-Oh. The definition is that $f(n) = O(g(n))$ if $|f(x)| ≤ M\,|g(x)|$ for a natural number $M$ and for sufficiently large values of $x$. Now, if $g(n) ...
2
votes
1answer
115 views

Variation of omega definition

The same question has been asked here Some authors define $\Omega$ in a slightly different way: let’s use $ \overset{\infty}{\Omega}$ (read “omega infinity”) for this alternative definition. ...
-1
votes
2answers
299 views

Big theta of $ \lceil{log(n+1)}\rceil $

I am trying to calculate the big theta of $ \lceil{log(n+1)}\rceil $. I derived the following inequality: $ log(n+1) \le \lceil{log(n+1)}\rceil \le log(n+1) + 1 $ Based on the definition of big ...
0
votes
2answers
343 views

Counterexample to big-O claim looks wrong

Let $T_1(n) = O(f(n))$ and $T_2(n) = O(f(n))$. Then $T_1(n) / T_2(n) = O(1)$ is a false statement. A counterexample is $T_1(n) = n^2$, $T_2(n) = n$, and $f(n) = n^2$. I don't get this ...
0
votes
0answers
38 views

Assymptotic notation equalities

Let f$(n)=O(n)$, $g(n)=\Omega(n)$ and $h(n)=\Theta(n)$. Then $g(n)+f(n)\cdot h(n)$ is equal to what among $O(n)$,$\Omega(n)$ and $\Theta(n)$? Also explain how to evaluate it.
3
votes
2answers
350 views

Conflicting definitions of quasipolynomial time

The textbook The Nature of Computation uses the following definition of quasipolynomial time: A quasipolynomial is a function of the form $f(n) = 2^{\Theta(\log^k n)}$ for some constant $k > 0$...
2
votes
2answers
35 views

Can I notate time complexity depending on the result of an algorithm?

I have a program that calculates the first year some two events happen on the same day. I have not calculated any upper limit for the year. The time complexity of the program would be equivalent to O(...
3
votes
1answer
98 views

Proving landau notation statements

If we have the function $f : \mathbb{N}_0 \rightarrow \mathbb{N}$ with $f(n) = n^2$ and we look at the following representations of the sets $\mathcal{o}(f),\mathcal{O}(f),\Theta(f),\Omega(f),\omega(f)...
0
votes
1answer
72 views

Can I say ≤ O(f(x)) rather than = O(f(x)) if the bound is not tight?

Suppose I just invented merge sort, but due to my limited ability was only able to prove that the running time is $O(n^2)$. However, I suspect that the running time is actually better (in reality it's ...
1
vote
1answer
50 views

Does the running-time of this push-relabel algorithm become zero if there are many edges?

According to the Wikipedia page on the Push-relabel maximum flow algorithm: Subcubic $O(|V||E| \log\frac{|V|^2}{|E|})$ time complexity can be achieved using dynamic trees, although in practice it ...
0
votes
1answer
3k views

How long will selection sort and merge sort take to sort a certain number of items?

I am dealing with a sample exam question that I cannot understand which is as follows: Selection sort takes one millisecond to sort 1000 items (worst-case time) on a particular computer. Estimate ...
0
votes
1answer
59 views

Big O notation question for set insertion with sequential scan?

A friend and I are asking some questions on Big O Notation. We have an operation that requires a sequential scan on insertion of an element O(n). The insertion itself of an element is O(1). We are ...
0
votes
2answers
4k views

The difference between dense graph and sparse one [closed]

How to decide whether the following statement is correct? O(E log E) and O(E log V) are equivalent regardless whether graph is dense or sparse
7
votes
2answers
341 views

Can you operate on and draw conclusions on functions described asymptotically?

This question is homework based (not using actual problem though)! Say you have a function described as: $$f(n) \in O(2n^2) \, .$$ Can you then go on the treat this as: $$f(n) = 2n^2$$ and ...
0
votes
1answer
883 views

Can g(n) be same for big O and omega notation for f(n) [closed]

I have been studying asymptotic notation and I understand that in big O notation $f(n) <=c1*g(n)$ and in omega notation we have $f(n)>= c2*g(n)$ where $c1$ and $c2$ are some constant. Now I ...
2
votes
3answers
1k views

If f(n) = Θ(g(n)) then what all can one say about f(h(n)) and Θ(g(h(n))

I was going across some problems which translated the fact that $\log (n!) = \Theta(n\log n)$ to give $$\log(\lceil\log n\rceil!) = \Theta(\lceil\log n\rceil \log \lceil\log n\rceil)$$ and therefore $\...
0
votes
1answer
409 views

Adding Big-O and little-o notation to get a little-o

Lets suppose that there exists a comparison-based algorithm that turns an arbitrary array to a state $A$ in $o(n\log k)$, and there is another comparison-based algorithm that turns an array in state $...
13
votes
1answer
7k views

What does tilde mean, in big-O notation?

I'm reading a paper, and it says in its time complexity description that time complexity is $\tilde{O}(2^{2n})$. I have searched the internet and wikipedia, but I can't find what this tilde signifies ...
0
votes
1answer
18 views

Determine time given algorithmic complexity as input grows?

Consider the time required to solve a problem, represented by f(n), and for sufficiently large inputs of size k, the time ...
2
votes
1answer
120 views

How does O transform this sum like that?

I'm in the process of self-studying the CLRS book. My mathematical background is poor so I'm trying to learn the maths as I go along too. I don't understand the math in CLRS section 6.4 where they go ...
0
votes
1answer
97 views

Complexity class for concurrent algorithms

We have the big O notations for sequential algorithms , but is there a notation to represent parallel algorithms in a similar way? Motivation: A sequential algorithm may be O(n7) but its parallel ...
3
votes
2answers
88 views

Asymptotic bounds on geometric sums

So I'm doing exercises from Dasgupta's Algorithms. The exercise i'm having trouble with is: Show that, if $c$ is a positive real number, then $g(n) = 1 + c + c^2 +...+c^n$ is: $\Theta(1)$...
3
votes
2answers
65 views

Is it possible to simplify $O(A \times B \times C + A^B)$ into $O(A^B)$

I am wondering if it is possible to simplify $O(A \times B \times C + A^B)$ into $O(A^B)$, i.e. omit the left part. $A$, $B$, and $C$ are all independent from each other. Personally, I think that the ...
2
votes
2answers
3k views

Dijkstra's algorithm runtime for dense graphs

The runtime for Dijkstra's algorithm implemented with a priority queue on a sparse graph is $O((E+V)\log V)$. For a dense graph such as a complete graph, there can be $V(V-1)/2$ edges. Since $E \sim ...
1
vote
2answers
1k views

big-O and Θ notation subset

I was reading “Introduction to Algorithms” by CLRS and it says Note that f(n) = Θ(g(n)) implies f(n) = O(g(n)) since Θ notation is a stronger notation than O notation. Written set theoretically, we ...
2
votes
4answers
315 views

Landau Notation: Why is O(f) (not) the set all g < c*f?

I am somewhat confused here about the Landau notations. Let's say we are dealing with function from $\mathbb{N}$ to $\mathbb{R}$. Then we can define $\mathcal{O}(f) = \left\{ g : \mathbb{N} \to \...
1
vote
1answer
114 views

In which O-class does my Θ-result belong?

In a multiple-choice test, I'm asked to solve the recurrence $T(n)=2T(n/2)+n/2$. I've done this using the master theorem: $f(n)=n/2$, $a=2$, $b=2$, so we're in the second case and $T(n)=\Theta(n\log n)...
0
votes
1answer
111 views

Out of these two algorithms. Is there always an input where A is faster then B? (Big theta notation)

I am currently learning landau notations and am stuck on the following True/False question. What seems a little confusing to me is the use of big-theta notation to describe worst-case run-time. What ...
5
votes
2answers
2k views

Big-O and not little-o implies theta?

If $f(n)$ is in $O(g(n))$ but not in $o(g(n))$, is it true that $f(n)$ is in $\Theta(g(n))$? Similarly, $f(n)$ is $\Omega(g(n))$ but not in $\omega(g(n))$ implies $f(n)$ is in $\Theta(g(n))$? If not,...
3
votes
2answers
1k views

Is $\log(n!)$ in $\Theta(n \log(n))$?

I had two questions on my automated test which I don't understand the answer for. $\log(n!) = \log(n\cdot (n-1)\cdot \cdots \cdot 2\cdot 1) = \log(n)+\log(n-1)+....+\log(1)$. So it is in $O(n\log(...
3
votes
1answer
34 views

Order Notation - Why can't $c$ be in terms of $n$?

For $f(n)$ to be in $O(g(n))$, there must exist a $c > 0$ and $n_0 > 0$ such that $$0 \leq f(n) \leq cg(n) \text{ for all }n \geq n_0\,.$$ I found a solution to a question where my $c$ is in ...
5
votes
3answers
615 views

Why does the square root of n! grow exponentially faster than exponential functions?

I am going through Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al. In the proof of the theorem $6$ of the paper on page 632, the authors go on ...