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

Asymptotic expansion of $\exp(-ax)\,\cosh(bx)$ or $\exp(-ax)\,\sinh(bx)$

I would like to understand the behaviour of $$\exp(-ax)\,\cosh(bx)$$ or $$\exp(-ax)\,\sinh(bx)$$ for large $x$, provided that $a,b>0$ and $a>b$ or $a
JFNJr
  • 1,055
0
votes
0 answers

Big theta notation Let P(n) = 1/3*n^5- 10*n^3+7*n-25.Formally prove that P(n) = theta (n^5).

First I tried to get the C2 by this: n=1 1/3n^5- 10n^3+7n-25 <= 1/3n^5+7n^5 = 22/3n^5 , C2=22/3 (I removed all the negative terms and multiplied the positive so I can get the max value, is this correct?) And then I tried to get the min value by…
DaDA
  • 1
0
votes
1 answer

Asymptotic notations

Iv'e been given this question: let $f,g:\mathbb{N} \rightarrow \mathbb{N}$ be increasing monotonic functions. Is it always true that $f\left( n\right) =\Omega ( g\left( n\right) )$ or $g\left( n\right) =\Omega ( f\left( n\right) )$ ? I can give a…
Tom Waller
  • 31
0
votes
0 answers

Big theta, comparing two operations

If $f_1(n) \in \Theta(g(n))$ and $f_2(n) \in \Theta(g(n))$, then $f_1(n) - f_2(n) \in \Theta(g(n))$. If this is true, prove it. Otherwise, provide a counterexample. Alright so my understanding is, a big theta operation basically means the…
Notthesmartest
  • 5
0
votes
1 answer

Is $a_n = o(n)$ different from $\max a_i = o(n)$?

Let $a_i$ be a sequence of real numbers. If I know that $a_n = o(n)$ as $n \rightarrow \infty$, is it equivalent to say that: $$\max_i^n a_i = o(n)$$ At first glance they seem different (the second seems stronger), but I think I am able to prove…
dmh
  • 2,958
0
votes
0 answers

Large $x$ behavior of a Taylor series with infinite radius of convergence

Given a Taylor series expression of a function $f(x)=\sum_{n=0}^{\infty}a_nx^n$, with an infinite radius of convergence, are there any basic/standard techniques for understanding the asymptotic behavior of the function as $x\to\infty$? How is the…
fewfew4
  • 827
0
votes
0 answers

Find time complexity for recursive function $T(n) = T(n-1) + (\log(n))^2, T(0) = 1$

I tried to unwinding the recursive function, but I got a $T(n) = 1 + (\log(1))^2 + (\log(2))^2 + ... + (\log(n-1))^2 + (\log(n))^2$ How can I simplify it, or can I get time complexity from other way?
Julie Guo
  • 11
0
votes
0 answers

little-o when a function vanishes

I understand the general definition of $f(x) \in o(g(x))$ which is usually given in the context when for $x \to x_0$ both $f(x)$ and $g(x)$ grow to $\infty$. In this "standard case" it means that $f$ grows at speed uniformly much slower than that…
PinkCollins
  • 21
0
votes
0 answers

Consequences of log equivalence

Suppose $11$. What can we say about the growth of $x_n$, besides that $\log x_n \sim n\log \rho$? I was interested mainly in figuring out if there is…
xyz
  • 960
0
votes
1 answer

Is it possible that $f(n) \not\in O(g(n))$ and $g(n) \not\in O(f(n))$

As the question stated, can I find any two functions $f(n)$ and $g(n)$ such that they satisfy: $f(n) \not\in O(g(n))$ $g(n) \not\in O(f(n))$
Bi Ao
  • 223
0
votes
0 answers

Prove for ∀C>0, C = Const and for ∀f function O(f(n)) + C = O ( f(n) + C ) = O(f(n))

for every C>0 where C is constant we need to prove that: O(f(n)) + C = O(f(n) + C) = O(f(n)) I am new to Big-Oh Notation and I would use any hint or guide how to deal with such things.
BMW BOI
  • 23
0
votes
1 answer

function $()$ that satisfies both $() ∈ (^3 )$ and, $() ∈ Θ(^3)$? (here $o()$ is little oh and $Θ()$ is big theta)

Does there exist a function $()$ such that it satisfies both $() ∈ (^3 )$ and, $() ∈ Θ(^3)$? (here $o()$ is little oh and $Θ()$ is big theta) Can some one help with a proof?
anomaly_0246
  • 1
0
votes
1 answer

is $f(x)$ in big-$O$ of $g(x)$ assuming the following?

Assuming that: $f(n)=O(g(n))$ and $f(n)$ and $g(n)$ are nondecreasing and always bigger than 1 Is the following necessarily true? $$f(n)\log_2(f(n)^c)=O(g(n)\log_2(g(n)))$$ And also, could you explain why? Thanks.
Wael Smith
  • 3
0
votes
1 answer

Little-o proof for $3n^2 = o(n^4)$

Logically, I know this affirmation to be true. For all $c$, there is a $n_0>0$ that will make $3n^2 < c n^4$. But when I try to prove it, I come to the resolution that it's false. Here is how I get this conclusion: $$f(n) \leq 3n^2 < n^4.$$ So we…
NearFinished_CS
  • 45
0
votes
0 answers

How to Prove $n=O(100n+n\sin(n))$

So I started learning about O notation and got this question Prove $n=O(100n+n\sin(n))$. I found it hard but still tried my best. \begin{align} n&=O(100 n+n \sin(n)),\\ n &\le c( 100n+n\sin(n)) , \ \ c=1 \\ n &\le 100n+n\sin(n) \\ 1 &\le …
BMW BOI
  • 23
1 2 3
…
74 75