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
1
vote
0 answers

How to find the influence function of $\int_{[0,t]}(1-F_\_)^{-1}dF$,i.e., cumulative hazard function

The common strategy is to replace $F$ with $(1-t)F+t\delta_x$ and then expand the integral. However, I am not sure how to deal with $F_\_$. It seems different from $F$.
user106240
  • 45
1
vote
3 answers

Show $f(x) = (x^4+x^2+1)/(x^3+1) $ is $O(x)$

How would I find the witnesses $C$ and $k$ such that $f(x)$ is $O(x)$? What I tried was $$(x^4+x^2+1)/(x^3+1) ≤ (x^4+x^4+x^4)/(x^3+x^3) = (3/2)x $$ for values $x>1$. $C = 3/2, k = 1$ Is this right?
Kris
  • 131
1
vote
3 answers

Asymptotic relationship demonstration

I have to demonstrate that if $$ \begin{split} f_1(n) &= \Theta(g_1(n)) \\ f_2(n) &= \Theta(g_2(n)) \\ \end{split} $$ then $$ f_1(n) + f_2(n) = \Theta(\max\{g_1(n),g_2(n)\}) $$ Actually I have already proved that $$f_1(n)+f_2(n) =…
user1868607
  • 939
1
vote
2 answers

Determine run-time of an algorithm

Probably a stupid question but I don't get it right now. I have an algorithm with an input n. It needs n + (n-1) + (n-2) + ... + 1 steps to finish. Is it possible to give a runtime estimation in Big-O notation?
user4811
  • 133
1
vote
1 answer

Using $\lim_{x \to \infty}$ to determine whether $f(x) = \Theta(g(x))$?

I'm learning it in the context of Running time complexity. to determine whether $f(x) = O(g(x))$, you can check whether the folloing limit:$$\lim_{x \to \infty} {f(x) \over g(x)} < \infty$$ if so, then you know that $f(x) = O(g(x))$. Is there a…
Billie
  • 3,449
1
vote
1 answer

Relationship Little '$\mathcal{o}$' and Big '$\mathcal{O}$'

I'm learning about asymptotic analysis and, as a starting point, big and little o definitions. On the Wikipedia page, http://en.wikipedia.org/wiki/Big_O_notation further down under the heading for little-$\mathcal{o}$ notation it states "In this way…
Jonathan Thurgood
  • 13
1
vote
1 answer

How to determine a $\Theta$-class of a Function

I have 6 functions that I have to determine which of 4 given $\Theta$-classes or neither of them. Example of a function I have been given: \begin{align*} \textit{$f_1$}(n) =&(17\textit{n}+1) \\ \end{align*} The $\Theta$-classes I have been…
cenh
  • 35
1
vote
1 answer

$T_{3}=\Theta(n^{0.99}) ,T_{2}=\Theta(n^{\log\log n}),T_{1}=\Theta\left(\frac{n}{\log n}\right)$

$T_{3}=\Theta(n^{0.99}),\quad T_{2}=\Theta(n^{\log\log n}),\quad T_{1}=\Theta \left(\frac{n}{\log n}\right)$ I need to decide what is the relation (ratio?) between $ T_{1},\, T_{2},\, T_{3}$? So by taking $\log$ on the three of them I came to…
user6163
1
vote
1 answer

To find condition on $p$ such that the asymptotics of a function is infinity

I came across the following asymptotic problem in my reseach, however I don't know how to answer it. Let $C_0,C_1,C_2,C_3$ be absolute constant (do not depend on $n$), and $p(n)$ is a function of $n$. We need to find $p(n)$ such that the following…
chloe
  • 512
1
vote
1 answer

Big O Multiplication by Constant

I have been working though CSE 373 Lectures by Skiena and I cannot understand his explanation of why multiplication by a constant does not change the asymptotics: $O(c*f(n)) \to O(f(n))$ In the lectures, Skiena gives the example with $c = 100$ and…
Mageentta
  • 15
1
vote
1 answer

Big O bound on the Tail of a Sum

Suppose we have a non-negative sequence $\{a_j\}$ such that $\sum_{j=1}^{\infty}a_j
Joseph Basford
  • 70
  • 1
  • 4
1
vote
1 answer

Transforming a sequence of i.i.d. variables so that its asymptotic distribution is non-degenrate

Suppose $X_1,X_2,\cdots$ are i.i.d. $U(0,\theta)$ random variables. Can you suggest a function $h$ of $X_1,\cdots,X_n$ and constants $a_n$ and $b_n$ such that $a_n(h(X_1,\cdots,X_n)-b_n)\xrightarrow{d}Y$ where $Y$ is a non-degenerate random variable…
QED
  • 12,644
1
vote
1 answer

Limiting Distribution of the given function

Can someone please help me in finding the limiting distribution of $$\frac{n(X_1X_2 + X_3X_4+\cdots+X_{2n-1}X_{2n})^2}{(X_1^2 + X_2^2+\cdots+X_{2n}^2)^2}$$ where $X_i$ are iid standard normal $\forall i\ge1$. I guess it has to be done using delta…
user87455
  • 81
1
vote
2 answers

Precise asymptotics of the sum of two square root functions

Question: Let $x_n$ be some term that goes to infinity as $n\rightarrow\infty$. I would like to know the precise asymptotics of $-\sqrt{x_n}+\sqrt{x_n+4}$. My attempt: We…
Resu
  • 764
1
vote
3 answers

Is big O always positive?

There is a function defined as follows: $x, y, w(u), w'(u)$ are all positive real values. $x > y \geq 2$. Does this mean that $\Phi(x, y) > \frac{x}{\log{y}}\left(w(u)+\left(\frac{y}{2x^2}-w'(u)\right)\frac{1}{\log{y}}\right)$ ? In other words, is…
Simd
  • 417
1 2 3
…
74 75