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
4 answers

Asymptotic for $x\ln(\sin(x))$ as $x\to 0$.

I need a non-singular way to evaluate $x\ln(\sin(x))$ as $x \to 0$. The limit is zero,but numerically I'm getting NaNs. How can I find a rapidly computable approximation to $x\ln(\sin(x))$ as $x\to 0$? It appears from the graph that $-C\sqrt{x}$…
user14717
  • 4,902
0
votes
1 answer

If $f(x) \in \Theta(g(x))$ can we imply that $f(x^2) \in \Theta(g(x^2))$ and $f(\log x) \in \Theta g(\log x)$?

My first thought is that it is, because $\Theta$ is a tight bound, so assuming a let's say $f(x) = x +2$ and $g(x) = x$, $f(x^2)$ should be bound by $\Theta(g(x^2))$. Same for the logarithm as well. However, I do need clarification about this for…
Master Boggins
  • 25
0
votes
1 answer

How to prove that $2^{n}$ is in $\omega$($n^{2}$) , by finding n in terms of c?

I am trying to prove the relationship mentioned in the title, only using the definition of $\omega$, but am getting stuck after taking the log of both sides of the inequality: $$cn^{2} \leq 2^{n}$$ I cannot seem to isolate for n, in terms of c, so…
Bob
  • 1
0
votes
1 answer

Does $(\frac{n}{4})^{\frac{n}{4}}$ have a higher asymptotic growth than $4^{n^{4}}$

I'm trying to determine how these 3 functions should be ordered in terms of asymptotic growth: $$f(n) = \left(\frac{n}{4}\right)^{\frac{n}{4}}$$ $$g(n) = n^{\frac{n}{4}}$$ $$h(n) = 4^{n^{4}}$$ $f(n)$ seems to be somewhat similar to $n^{n}$ and that…
Programmer Failure
  • 35
0
votes
2 answers

How to prove big O notation

How can I prove that $f_1(n) = n^{0.999999} \cdot \log_2n$ is $O(f_2(n))$ where $f_2(n) = 1.000001^n$? I'm trying to understand how to prove when a function is O of another one, but I don't get what I'm supposed to do.
Programmer Failure
  • 35
0
votes
1 answer

prove the statement (big O notation)

Prove the following statements: $2^n$ is $O(n!)$, and $n!$ is not $O(2^n)$ not sure where to start with these two... thanks
Supernatural
  • 361
0
votes
2 answers

Show that there exists a constant $c>0$ so that $f(n) \le cg(n)$ for every $n\ge 1$

Given two positive functions $f(n)$,$g(n)$, such that $f(n)=O(g(n))$ (big O notation) show that there exists a constant $c>0$ so that $f(n)\le cg(n)$ for every $n\ge1$ I dont know how to solve this because I learned at class that $n$ can start start…
KIMKES1232
  • 425
  • 3
  • 9
0
votes
0 answers

Derivative of Little o

I know that it is in general not true that if $f(x) = o(x^n)$ it follows that $f'(x) = o(x^{n-1})$ or in other words: $f(x) = o(g(x))$ does not imply $f'(x) = o(g'(x))$. But is it still possible to relate those two quantities together? E.g. by…
Syd Amerikaner
  • 447
0
votes
1 answer

Asymptotic bounds

Is it right to say that suppose we have two monotonically increasing functions $f,g$ so that $f(n)=\Omega(n)$ and $f(g(n))=O(n)$. Then I want to conclude that $g(n)=O(n)$. I think that this is a false claim, and I've been trying to provide counter…
david kokiashvili
  • 13
  • 5
0
votes
1 answer

Big O notation of sums

I have two summations in a paper I'm reading $$ \sum_{i=j}^{n-1}\frac{n}{i-1} $$ and $$ \sum_{i=j}^{n-1} \left(\frac{n}{i+1}\right)^2\left(1 - \frac{i+1}{n} \right) $$ and their big O notations are $n\log n + O(n)$ and $O(n^2)$ respectively. They…
hyperman
  • 21
0
votes
1 answer

Computing Big O for a given function/ Figuring out the more relevant term of a function

Considering we have a function: $$ f_{n, m} : \mathbb{N ^ 2} \rightarrow [0, 1]\\ \{n, m\} \in \mathbb{N ^ 2}\\ f_{n, m}(x, t) = {m \choose x} \cdot \prod_{j=0}^{x-1} \dfrac{t-j}{n-j} $$ We want to find find out which of the two terms($x$ and $t$)…
Sergiu Nistor
  • 5
0
votes
0 answers

Is $O(n-d) = O(n)$ true?

Say we have a variable $n > 0$ and a constant $d \geq 0$. Is is then true that $O(n-d) = O(n)$?
That Guy
  • 1,309
0
votes
1 answer

Limit of $\hat \sigma_n/\log(\log(n))$

Let $X_i$ be a sequence of iid rv with finite variance and $\hat \sigma_n = \sqrt{\frac{1}{n}\sum_{i=1}^n(X_i - \bar X)^2}$. By a LLN, $\hat\sigma_n\rightarrow \sigma$ as $n\rightarrow\infty$. But what about $$\frac{\hat\sigma_n}{\log(\log(n))}?$$…
Syd Amerikaner
  • 447
0
votes
1 answer

Confusion about the definition of $f(n) \in O(g(n))$

I learned in my Algorithmics course that that : $f(n) \in O(g(n))$ can be written as $f(n) \leq cg(n)$. My confusion is about what $c$ is. Is it a constant that can be any value? Is it a constant that can be changed depending on which value of…
BreezeWind
  • 183
0
votes
0 answers

Is k^3 O(n^2) for some constant k > 1?

On the one hand a constant should be upper bounded by a variable which increases. But I'm not really sure if this is the case, as $k^3$ is a higher power than $n^2$. I'm don't know how to approach this problem as I don't really know take the limit…
Alec
  • 354
1 2 3
…
74 75