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

the difference between big and small asymptotic notation

I saw this example and i am a little confused. $10n^2-5n+6046$=$ω(n^2)$ isn't that a mistake and it is necessary to use $Ω$? because $n^2$=$n^2$
postFix
  • 257
0
votes
4 answers

Intuition on what $(1-o(1))$ means.

Does $(1-o(1))$ imply something very close to $1$ or something very close to $0$. I understand that $o(1)$ means a function growing at less than 1. Thanks for your help.
Jerome Turner
  • 555
0
votes
2 answers

Prove that $\Bigl( 1 - \frac{1}{x} \Bigr)^{\frac{x}{\ln x}} = 1 + O \Bigl( \frac{1}{\ln x} \Bigr)$

It was my first attempt to use $\lim\limits_{x \rightarrow \infty} \Bigl( 1 - \frac{1}{x} \Bigr)^{x} = e^{-x}$. But then I didn't know what to do with $\frac{1}{\ln x}$. On my second try, I wanted to use \begin{align*} \Bigl( 1 - \frac{1}{x}…
Lisa
  • 9
0
votes
1 answer

$f \in O(\log(n))$?

How can I find the complexity of i = 1; while( i
Alex
  • 376
0
votes
1 answer

Can a function be big Oh and big theta of another function?

I'm trying to understand if a function $f(n)$ can be both $O(g(n))$ and $\Theta(g(n))$.
Khadar111
  • 11
0
votes
0 answers

Find all the asymptotes of the equation

Find the alll asymptotes of the equation $$x^3-x^2y-xy^2+y^3+2x^2-4y^2+2xy+x+y+1=0.$$ Here's what i tried: Equation for oblique…
Ayush Kumar
  • 11
0
votes
2 answers

What is the best theoretical Big O for some ideal algorithm?

Big O notation has many commonly found real-world examples, like O(N), O(log N), O(N log N),... and so on. Other than a constant Big-O like O(1), is there some theoretical golden "value" of O that some perfectly efficient algorithm could achieve,…
FShrike
  • 40,125
0
votes
1 answer

Excercise: Ordering functions using the BigO notation

This was one of the previous year's exam questions. I have to order the following functions according to their growth rates using the $\mathcal O(n)$ notation. $f_1(n) = 2010 * \log_3(n^n)$ $f_2(n) = n^{1+2+...+ \log_2 \log_2 n }$ $f_3(n) =…
noname
  • 3
0
votes
2 answers

Asymptotically $n(1-\frac{a\log n}{n})^{n/2-1}(1-\frac{b\log n}{n})^{n/2}\sim n^{1-\frac{a+b}{2}}$

Suppose $a,b>0$ and $\frac{a+b}{2}<1$ Why is the following relation true as $n\rightarrow\infty $ $$n(1-\frac{a\log n}{n})^{n/2-1}(1-\frac{b\log n}{n})^{n/2}\sim n^{1-\frac{a+b}{2}}$$ The $1$ in the exponent on the right hand side value is obviously…
H. Walter
  • 979
  • 4
  • 9
0
votes
1 answer

What is the rule about the log of small o notation?

Say I have the MacLaurin Series expansion of a function and get \begin{equation} 1+2f(0)c_is_i\theta+o(\theta) \end{equation} and I want to take the log of this function -i.e. $\log[1+2f(0)c_is_i\theta+o(\theta)]$. How would the last term be…
Carl
  • 173
  • 4
0
votes
1 answer

How do I calculate Big Omega Notation for a function?

I was looking at the definition of Big Omega: \begin{align} \Omega(g(n)) &= \{ f(n): \text{ there exist positive constants }c \text{ and }n_0 \\ &\ \ \ \ \ \ \ \ \text{ such that }0 \le cg(n) \le f(n) \text{ for all }n \ge n_0…
Alfred
  • 103
0
votes
1 answer

Show that $(\log n)^{\log n}\in\Omega (n)$

Show that $(\log n)^{\log n}\in\Omega (n)$ Proceeding with a common logarithm property, we get $$(\log n)^{\log n}=(n^{\log\log n})$$ How do I deduce that $$(n^{\log\log n})\in\Omega(n)$$ If I say that $n=b^{b}$ where $b$ is the base of the…
Anindya Prithvi
  • 1,194
0
votes
1 answer

Prove $\forall \epsilon >0 \quad log(log(n)) = O(log^\epsilon(n))$

I need to prove that $$\forall \epsilon >0 \quad log(log(n)) = O(log^\epsilon(n))$$. I started by citing a known result which is (*) $$\forall \epsilon >0 \quad log(n) = O(n^\epsilon)$$ Then we can say that $\exists n_0, c$ such that $\forall n>n_0…
Eliran Turgeman
  • 183
0
votes
1 answer

Comparing functions using asymptotic notations

I am learning algorithmic analysis and I want to know how to compare functions...I am trying to apply the definitions of Big Oh, Omega and theta yet unable to find the correct answer. For example, how to know if $f(n) = 100n^{5.001} +…
Slavbabushka69
  • 3
0
votes
1 answer

Clarity on Big-O

so I just had this question, I know that for example $g(n) = 100$, then $O\big(g(n)\big) = O(1)$. Let us take $a(n)$ as some function like $n\log n$, does this mean that $a(n)\in O\big(g(n)\big)$?
Hey there
  • 3
1 2 3
…
74 75