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
1 answer

What is the vertical asymptote of $y=2x-\arccos(\frac{1}{x})$?

I have to find the vertical asymptote of $y=2x-\arccos(\frac{1}{x})$. So I have to find the limit of the function when $x$ approaches zero. In my textbook it says that the vertical asymptote does not exist for this function ..why? For $x\to0$ the…
eeweew
  • 21
0
votes
1 answer

Determining minimum problem size "n"

my problem is: The execution time of the first algorithm can be given as a function of the input size $n$ as $f(n) = n^{1.5} \log^2 n$. The execution time of the second algorithm is similarly: $g(n) = n^2$. Find the minimum problem size $n$ needed…
L. Li
  • 59
0
votes
0 answers

Landau notation (big and little)

Suppose $(x_n)_{n\in\mathbb{N}}$ is a non-negative zero sequence and $x_n<\frac{\log(n)}{n}$. Consider a function $f(x_n)=O(x_n^2), n\to\infty$. Am I right, that we can conlude that $$ f(x_n)=O\left(\frac{\log(n)}{n}\right), n\to\infty $$ but…
Salamo
  • 1,094
0
votes
2 answers

Verifying an asymptotic sequence

I want to verify that i) $\phi_n (z) = ln(1+z^n)$ as $z \rightarrow 0$ ii) $\phi_n (z) = z^ne^{-nz}$ as $z \rightarrow \infty$ are both asymptotic sequences. The term 'verify' somewhat confuses me in terms of what would be considered sufficient…
Evan
  • 663
0
votes
1 answer

Induction proof for a recurrence relation in big O notation

Let $T(n)$ be defined recursively by $$T(1) = 4 $$ $$T(n) = 2T(\frac n2) +5n,\qquad n\geq 2 $$ Prove T(n) is = O(n*log(n), Log is always base 2, so Log base2 (n) T(n) <= C * n * log(n) for all n >= k …
Tim Case
  • 1
  • 1
0
votes
0 answers

Big-O Notation of an expression

I have the expression $$ \frac{1}{A}\left(\ln x + \sqrt{2(\ln x-1)}\right),$$ where $A$ is a positive constant with respect to $x$. I want to isolate the dominant term and add the error term in O-notation for $x \rightarrow \infty$. Can someone…
N. Younger
  • 173
0
votes
0 answers

Series for roots

The sequence of polynomial equations $$ (a+n)x^n+(b-n)x^{n-1}+f(n)=0 $$ has real roots near 1 having an asymptotic series $$ x_n=1+\frac{y_n-a-b}{n}+O(y_n^2n^{-2}), $$ where $$ y_n=W(-e^{a+b}f(n)). $$ Here $W$ is the Lambert function. Now, I want…
Rhjg
  • 2,029
0
votes
2 answers

Solving $T(n)=T(n-1)+c\cdot \log n,\quad T(1)=d$

Solving $T(n)=T(n-1)+c\cdot \log n,\quad T(1)=d$ Attempt: I tried iteration method: $$T(n)=\color{blue}{T(n-1)}+c\cdot \log n,\quad T(1)=d$$ $$\color{blue}{T(n-1)}=\color{red}{T(n-2)+c\cdot \log (n-1)}$$ $$T(n)=\color{red}{T(n-2)+c\cdot \log…
Error 404
  • 1,892
  • 1
  • 11
  • 23
0
votes
0 answers

How to formally to show one term is lower order than the other terms

I have the following mathematical expression: \begin{align} f(n,m, a)=\frac{1}{n}+\frac{1}{m}+ \frac{a_{n,m}}{(n+m)S_{n,m}} \end{align} As $n$ and $m$ increases to infinity, $a_{n,m} \overset{p} \rightarrow 0$ or $a$ converges in probability to 0.…
Vincent
  • 139
  • 5
0
votes
2 answers

An easy way to argue $((n+1)\log_2(n+1)-n) = \mathcal{O}(n*\log(n))$

I'm looking for an easy way to prove that $((n+1)*\log_2(n+1)-n) = \Theta(n*\log(n))$. I've used the limit definition of $\mathcal{O}$ with L'Hôpital's rule on this, but I find this rather exhaustive. Is there an easier way to do this? Thanks for…
3nondatur
  • 4,178
0
votes
1 answer

Big O to compare functions

Say we have the following: $$f(x) = \log(x)$$ $$g(x)= \log(20x)$$ If we want to compare the two using big O notation, does this mean that I have to keep the factor $20$ so that I can conclude that $f(x) = O(g(x))$? I'm a little confused since when…
O_O
  • 129
0
votes
2 answers

BIG-O proposed proof

I would like to prove that the statement $40^n = O(2^n) $ is false Would the following suffice as a proof? Let k be some arbitrary number. Let c = $\frac {40^k}{2^k}$. Then if n>k $\frac {40^n}{2^n}=\frac {40^k}{2^k}*\frac {40^{n-k}}{2^{n-k}}$. Then…
bosra
  • 561
0
votes
1 answer

Prove $O(n+\log(n)) \subset O(n \cdot \log(n))$

How do I prove the following? $$O(n+\log(n)) \subset O(n \cdot \log(n))$$ I've plotted both functions and I see that $n+\log(n)$ is below $n \cdot \log(n)$. Can limit help me here? $$\lim_{n \to \infty}\frac{n+\log(n)}{n \cdot \log(n)} = 0$$ If so,…
user518597
0
votes
1 answer

Big Oh calculation

I'm wondering if someone could break down this big O notation for me because this still kind of eludes me. Two data frames: A of size n x 2 and B of size m x 2, both of type numeric. Assume each row is a coordinate pair. We must find which…
conv3d
  • 161
0
votes
0 answers

Dominant term of $f(x)=\frac{a}{a+ax+(1-a)\sqrt{x}}$, where $0\le a \le 1$, $x>0$ when $x\to 0$

If I have a function $$f(x)=\frac{a}{a+ax+(1-a)\sqrt{x}}$$ where $0\le a \le1$, $x>0$. Then, what's the dominant term in denominator when $x\to 0$?
Dave
  • 576
1 2 3
…
74 75