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

Lowest Big-O of 3^n^3

Figuring out the lowest Big-O for $\ 7n^2$ for example, is straight-forward by finding witnesses C and k such as $\ n > 7 $ therefore $\ 7n^2 < n^3 $ so k = 7 and C = 1. So $\ 7n^2 $ has Big-O($\ n^3$) But, how do I find the lowest Big-O for…
Patrick.SE
  • 157
1
vote
2 answers

Is $n^{\log \log n}$ polynomial in $n$?

Is $n^{\log \log n}$ polynomial, exponential or subexponential in $n$?
stefan
  • 1,030
1
vote
0 answers

Comparing Big $O$ notation of functions $f(n) = n^2$ and $g(n) = n^3$

On the question Big O Notation "is element of" or "is equal" it is said that Example: you have two functions $n↦f(n)=n^3$ and $n↦g(n)=n^2$ Obviously f is asymptotically faster than g. [...] $f(n)∈O(g(n))$ Why is it "faster" and not "slower"? I am…
Xaphanius
  • 155
1
vote
1 answer

finding local behaviour as x tends to $0^+$ of particular solution of ode

we have $$ y' + xy = \cos x $$ I am asked to find the first three terms in local behaviour as $x \to 0^+$. thought: As $ x \to 0^+$, then $\cos x \sim 1 $ so $$ y' + xy \sim 1 $$ which can be solved by using integrating factor $e^{x^2/2}$, thus $$ (…
user139708
1
vote
1 answer

Relation between two asymptotics

What is is the largest $0
Elliot Gorokhovsky
  • 2,107
1
vote
2 answers

Big O -- mathematical Proof with a summation series

I am looking to prove that for every fixed value of $k$, $$ n^{k+1}= O(1^k + 2^k + \cdots + n^k) $$ I have already proved that $1^k + 2^k +\cdots + n^k =O(n^{k+1})$ but I don't know how to make the jump to proving the opposite is true. I was…
usernolan
  • 69
1
vote
1 answer

Comparing asymptotic order of logarithmic functions

If I have two complicated logarithmic functions, say $\sqrt{\log n}$ and $\log(n(\log n)^3)$, and I have to compare them in terms of their asymptotic order. How do I do that? Do I have to create graphs, or is there another definitive way of doing…
Parth Mody
  • 111
1
vote
0 answers

Invert big-O involving logarithms while retaining a good error term

I have an equation $$ y=\frac{kx}{\log(y/k)-1}+O(1) $$ which I would like to solve for $y$ in terms of $x$ ($k$ is constant). Clearly $y\sim kx/\log x$ but I would like to preserve the error term. Can this be done? I can iterate a few times but that…
Charles
  • 32,122
1
vote
0 answers

Why does O(1 + 2 + ... + n-1 + n) = O(n^2)?

Looking at the example on this page, I see that we can solve the recurrence relation T(n) = T(n-1) + O(n) like this: T(n) = T(n-1) + O(n) = (T(n-2) + O(n-1)) + O(n) = T(n-2) + O(n-1) + O(n) = …
Orange
  • 11
  • 2
1
vote
0 answers

Can you get the following asymptotics?

Consider $$ e^{N/d}\frac{d}{2N}\sum_{n=0}^{N-1}\left(\frac{d}{N}\right)^nn! $$ I know its asyptotics when $d
PhoenixPerson
  • 717
1
vote
1 answer

A Big O Conundrum

Is it in general true that $O((x-a)^n) = O(x^n)$? I have the feeling that the answer is no because I can only make the following be true if $x\geq a$: $f(x) = O((x-a)^n) => |f(x)|\leq K|(x-a)^n|\leq K|x^n|$ If someone can confirm or say otherwise,…
plebmatician
  • 846
  • 7
  • 19
1
vote
1 answer

Are any of these functions of the same order?

I ordered these functions by their asymptotic growth rates from smallest to largest. $$\sqrt{2}^2, \log_{10}n, n^{1/2}, \log_2n^2, \log_2n^n,n^2, 2^n, (\log_2n)^n.$$ I am trying to figure out how to tell if any of them are in the same rate category?…
MathIsHard
  • 2,733
  • 16
  • 47
1
vote
0 answers

Running time function

I'm trying to learn and understand how to find big O notation . well, here I need to find big-O notation for these algorithms , and I did the calculating for the running time for these algorithms but I'm not sure if my attempt is correct or…
stephan
  • 11
1
vote
1 answer

Proving that $f(x)$ is not $O(\log f(x))$

I tried to prove (by contradiction) that, given a positive function $f(x)$, it is not $O(\log(f(x))$ (in this case, log denotes the base 2 logarithm). The problem is that I do not know anything about the behaviour of the function (and therefore…
Alan Bletchley
  • 11
1
vote
1 answer

How to prove that a function f(n) exists/belongs to bigTheta?

So as per the title, I'm trying to prove that a function $f(n) = n^2 + 8n$ exists in $\Theta (n^2)$. What I'm having trouble with is the logic/concept behind doing so. By definition, it would mean that: $c_1n^2 \leq n^2 + 8n \leq c_2 n^2 $for…
Vance
  • 13
1 2 3
…
74 75