Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [asymptotics]

For questions involving asymptotic analysis, including function growth, Big-$O$, Big-$\Omega$ and Big-$\Theta$ notations.

Questions involving asymptotic analysis, including function growth, Big-$O$, Big-$\Omega$ and Big-$\Theta$ notations.

  • $f(x) = O(g(x))$ as $x \to \infty$ is used to mean that for sufficiently large values of $x$, we have $|f(x)| \leq A g(x)$ for some constant $A$.

  • $f(x)=\Omega(g(x))$ is equivalent to saying that $g(x)=O(f(x))$.

  • $f(x)=\Theta(g(x))$ is used to mean that $f(x)=O(g(x))$ and that $f(x)=\Omega(g(x))$.

9469 questions
0
votes
2 answers

How would I go about proving these.

I need to prove or disprove these two problems, but I'm not sure I did it right. $$(a).\quad f(n) = 2^n+1 = O(2^n)\\ (b).\quad f(n) = 2^n+1 = Θ(2^n) .$$ What I tried for the first one is, $2^n+1/2^n \le C$ when $K>1$, and then get stuck. I…
John
  • 71
0
votes
1 answer

Big-O Constants Rule Question for not-monotonically non-decreasing functions

I know that for positive monotonically non-decreasing functions, f(n) and g(n), f(n) = O(g(n) + c) entails f (n) = O(g(n)) Why does this always true only for positive monotonically non-decreasing functions? If there exists one, give a…
STC
  • 11
0
votes
2 answers

Please provide additional information for a Big-O problem solution

I am studying a Big-O example but I just do not get the idea. I have already seen that this question was asked in this forum but I am still confused. Can someone please provide another explanation so I can have more options to analyze? My main…
JORGE
  • 341
0
votes
1 answer

How do I determine a percentage increase of a function caused by increasing the input?

Suppose you have algorithms with the five running times listed below. (Assume these are the exact running times.) How much slower do each of these algorithms get when you (a) double the input size, or (b) increase the input size by one? a) $n^2$ b)…
mylasthope
  • 241
0
votes
0 answers

Different Upper and Lower Bound

Is there a function or algorithms whose upper bound and lower bound are different? For example f(X) i.e f(X) = O(X^2) and f(X) = Omega(X)
user1918858
  • 131
0
votes
2 answers

Dominance and Big Oh problem

What is the dominant term in the following expression? 100n + 0.01*(n^2) It is confusing because the power function should be growing faster than the linear function regardless the constants. But trying to sketch both functions on the same graph…
A_Matar
  • 103
0
votes
2 answers

Big $O$ notation - $n ^ {\log n}$ versus $2^n$

I received an asymptotics question for my homework, which is to compare the orders of growth for $f(n)$ and $g(n)$ where: $f(n) = n^{\log(n)}$ $g(n) = 2^n$ I have an intuition that $f(n) = O(g(n))$, and plotting the functions on a graph suggests the…
peco
  • 111
0
votes
2 answers

How to justify adding and multiplying relations with big-O?

I know that it's valid to add and multiply functions in Big O, although I haven't seen a proof why. As such I think this is a valid starting point. However, I have no idea how to progress and any help would be much appreciated.
user212880
  • 3
0
votes
1 answer

Order of trig functions as $x \rightarrow 0$

In my notes it was given that as $x\rightarrow 0,$ $$\frac{x^{3/2}}{1-\cos x} = \mathcal{O}(x^{-1/2})$$ It didnt give any explanation, so I was wondering what would the "method"/"intuition" be behind it, to be able to deduce/find out that…
Heijden
  • 331
  • 1
  • 3
  • 12
0
votes
1 answer

Need explanation on asymptotic running time results for various functions

I did not understand few results from the book problem. Here is the problem: Indicate, for each pair of expressions (A, B) in the table below, whether A is O, o, Ω, ω, Θ of B. Assume that k ≥ 1, > 0, and c > 1 are constants. And solution: I am not…
UserMoon
  • 349
0
votes
1 answer

Orders of Asymptotes

We know that $\log(X)^n = o(X^\epsilon)$ for all $n,\epsilon>0$. My questions is, is $\log(X)$ the largest function that is smaller than all (small) powers of $X$. That is, can we find a (non-trivial) function $f$ such that $$\log(X)^n \ll f(X) \ll…
Mastrel
  • 1,487
0
votes
1 answer

Time complexity and Stirlings approximation

We have an operation that is $O(\sum_{i=1}^{n^2}\log(i))$. Is this valid?: $= O(\log (n^2!)) = \{\text{Stirling}\} = O(\log((n^2)^{n^2})) = O(n^2 \log(n^2)) = O(n^2 \log(n))$ If so, what's an 'easier' argument?
Benjamin Lindqvist
  • 3,112
0
votes
1 answer

Why $\frac{1}{nh}O(h)=o[(nh)^{-1}]$ and $O_p(h^2+(nh)^{-1/2})=o_p(1)$

Suppose that we know: as $n\to\infty$, $h\to 0$ and $nh\to\infty$. Why does it follow that $\frac{O(h)}{nh}=o[(nh)^{-1}]$, $O_p(h^2+(nh)^{-1/2})=o_p(1)$? I'm learning kernel density estimation from Li and Racine (2007). The above appeared on…
yurnero
  • 10,505
0
votes
1 answer

Big oh notation

I am learning big-oh notation and i am wondering if something like $O(\sqrt{x})=O(O(\sqrt{x}))$ is true, and, more importantly, how you can prove this rigorously using the definition of big-oh? Another example is $O(\frac{2x-3}{\log…
Ninja Boy
  • 3,133
0
votes
1 answer

Explain why $f = O(g)$ for $f(n) = (2^{n} + 2n^{2})^{1/5}$ and $g(n) = 4n^{5} + 8n + 2\log(n)$

I am working on a review for a test and I'm trying to figure out how to explain the following problem: Determine if the following statement is True or False. Briefly explain why: If $\,f(n) = (2^{n} + 2n^{2})^{1/5}$ and $\,g(n) = 4n^{5} + 8n +…
steveclark
  • 229
1 2 3
…
74 75