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

Estimate cardinality of the set

Prove that: $$\left|\left\{ \langle a,b \rangle\in \mathbb{N}\times\mathbb{N}:a^2+b^2\le n \right\}\right|=\frac{\pi}{4}n+O(\sqrt{n})$$ I heard something about that the number of lattice points under the graph of a function is asymptotically equal…
ray
  • 1,507
1
vote
1 answer

Big-O complexity of multiple variables with different functions

I am trying to figure out what is the total Big-O complexity of a problem with multiple variables and different mathematical functions. The two big steps in the problem takes O(n*m) and O(n*logn). Both n and m are independent and can be very big or…
Tom Forde
  • 13
1
vote
1 answer

big-o notation - prove that $3n^2 - 1$ is or is not $O(n^2)$

Is $3n^2 - 1$ is or is not $O(n^2)$? I tried to solve it by adding the constants to get $c: 3 + 1 = 4; c = 4$. If $n \geq n_0$ and $n_0$ is $1$, $3n^2 - 1 \leq 4n^2$. However, to disprove it, I tried to substitute zero to the equation: $3n^2 - 1…
user1764381
  • 113
1
vote
2 answers

Asymptotic evaluation

I need to compare (asymptoticly) between $\left ( \frac{\ln n +4 \ln\ln n}{\ln n} \right )^{\ln n}$ and $16^{\ln\ln n}$. The options are $\Theta , \omega, o$. My work so far: I denoted $t_n=\ln n$ to make things cleaner. The first sequence is $\left…
35T41
  • 3,377
1
vote
1 answer

Big O-Notation Proof Omega and Theta

Consider the following three functions $ f,g,h: \mathbb{N{}} \rightarrow \mathbb{R} $, for which applies: $ f \in \Omega(g) $ and $ g \in \Theta(h) $. Proof or disprove formal that $f \in \Omega(h) $. I think that it is clear that $ f \in \Omega(h)…
peter87
  • 47
1
vote
0 answers

Finding a degree-2 polynomial that sits under the Harmonic Numbers.

Does there exist a degree-2 polynomial with positive acceleration such that the real extension of the harmonic numbers surpasses it for all future values? This was too big of a title and it's a really big mouthful, so I'll further elaborate on what…
Axoren
  • 2,303
1
vote
2 answers

Show that $k\ln k \in \Theta(n)$ implies $k \in \Theta(n/\ln(n))$?

It is exercise (3.2-8) from Introduction to Algorithms book. I need help to solve it. I am confused by the fact that there are two parameters. Because usually one parameter is used. There is related exercise which can be helpful. Thanks.
Sergey Sokolov
  • 157
1
vote
1 answer

How to proof $n^2+n \in \Theta(n^2)$?

It stands to reason that $n^2+n \in \Theta(n^2)$. But how can I formally proof it? I tried next way: Generalized to $$f(n)+o(f(n)) \in \Theta(f(n))$$ Separated to $$\tag{1} f(n)+o(f(n)) \in O(f(n))$$ $$\tag{2} f(n)+o(f(n)) \in…
Sergey Sokolov
  • 157
1
vote
0 answers

Why is $\frac{1}{1-x} = 1 + \Theta(x)$ for $x \in (0,1)$?

I am trying to understand the statement $$ \frac{1}{1-x} = 1 + \Theta(x) $$ for $0 < x < 1$. To my understanding, this could mean two things: There are constants $C_1$ and $C_2$ such that $1+C_1 x \leq \frac{1}{1-x} \leq 1 + C_2 x$ for all $x \in…
user133281
  • 16,073
1
vote
1 answer

Proof of Property of little o

I am learning some asymptotic analysis and i'm trying to prove: If $\lim_{x\to c} f(x)< \infty$ then $o(fg)=o(g)$ (as $x \to c$). So far i have proved that $o(fg)\subset o(g)$, but i am stuck on the other set inclusion. Is it possible that this is…
Nap D. Lover
  • 1,207
1
vote
1 answer

Proof involving the Big-O notation

I am stuck on a proof question involving the big-O notation: Prove that if $f(x)$ is $O(x^3)$ then $f(x+x^2)$ is also $O(x^3)$. I am stuck because $f(x)$ can be any arbitrary polynomial. I started off with defining $f(x)$ as a polynomial of the nth…
mathnoob
  • 21
1
vote
1 answer

Why is $O(x^{\alpha + \epsilon}) \neq O(x^{\alpha})$ if $\epsilon$ is arbitrarily small but greater than $0$?

There are several equivalent formulations of the Riemann hypotheses that utilize the big O notation. For example, it is known that $M(x) = O\left(x^{\frac12+\epsilon}\right)$ for all $\epsilon > 0$, where $M(x)$ is the Mertens function is equivalent…
Daniel R
  • 3,199
1
vote
1 answer

Is it true $ 2^{2^n} = O(2 ^n )$?

I have some problem to solve this question. Intuitively, I think not, but I'm not sure. If a log the lelf a have $2^n \log2 <= 2^n$ That's ok ?
Luan Oliveira
  • 113
1
vote
0 answers

Asymptotic bounds of product of $\log(i)$

$$\prod _{k=2}^n\left(\log_2k\right)$$ Can somebody help me with bounds of this expressions. I see only the rude measure: $$\log_2n\le \prod _{k=2}^n\left(\log_2k\right)\le \left(\log_2n\right)^n$$
Ilya.K.
  • 1,288
1
vote
1 answer

Simple asymptotic analysis problem

I came across a problem that I tried to formalize as follows: Let say i have two functions $x(t)$ and $y(t)$ such that for $t \rightarrow t_0$ $$ \left\{ \begin{array} \;y(t) \rightarrow -\infty \\ x(t) \rightarrow -\infty \\ y(t) =…
user8469759
  • 5,285
1 2 3
…
74 75