# Tagged Questions

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

48 views

46 views

32 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 ...
519 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 ...
54 views

### Need help understanding a derivation of “witnesses” for a Landau bound

So here's an excerpt from Foundations of Computer Science by Alfred Aho and Jeffrey Ullman[1]. I've also found basically the same material in a few other places, and also in my discrete math textbook, ...
2k views

### What does Θ(1) memory mean?

I have the definition of an in-situ algorithm from the professor, but I don't understand it. In-situ algorithms refer to algorithms that operate with Θ(1) memory. What does that mean?
54 views

217 views

### Show that if d(n) is O( f (n)) and e(n) is O(g(n)), then d(n)−e(n) is not necessarily O( f (n)−g(n)) [duplicate]

I have this question as an assignment in my Java Algorithms class, and i'm aware that d(n)+e(n) is the same as O(f(n)+g(n)). I dont know why the same doesnt apply to subtracting. Can someone help me? ...
51 views

331 views

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

What does $\log^{O(1)}n$ mean? I am aware of big-O notation, but this notation makes no sense to me. I can't find anything about it either, because there is no way a search engine interprets this ...
95 views

I am confused as to how this is true: O(n log n) + mO(log n) = O((m + n) log n) I understand that O(n) + O(m) = O(n + m). I'm mostly confused as to how to deal with the coefficient preceding O(log n)....
78 views

### What does Big O notation actually specify? [duplicate]

Regarding time complexity I've read conflicting things: 1) That it is worst case. 2) That is average case. For example if I want to know the time complexity for inserting into an arbitrary point in ...
103 views

### Big-O Notation Statement True? [duplicate]

Considering functions f and g, is the following true? $(f \in O(g)) \implies (f \in \Theta(g)) \lor (f \in o(g))$ If not, can you please state an example? Despite thinking hard, i could not find ...
46 views

### What's the formal definition of Big-O notation for functions of more than one variable?

For functions of a single totally ordered variable, I already know that $f(n)$ is $O(g(n))$ if and only if $\exists m. \exists c. \forall n. (n \ge m) \rightarrow [ f(n) \le c \cdot g(n) ]$. What I ...