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

Let $f(n) = n^{(n+1)}$ can we say that $f(n)$ is $O(n^n)$

Let $f(n) = n^{(n+1)}$ can we say that $f(n)$ is $O(n^n)$? To solve this problem I am using the Big-Oh definition: We must find $c_1$ and $N_0$ such that $f(n) \leq C_1 \times n^2$ for $n \geq N_0$ My Attempt: I say that we cannot say that $f(n)$ is…
Arthur Green
  • 167
0
votes
2 answers

Proving big-O notation?

$2n^2 \in O(n^2-19n)$ This was proven in my lecture notes but it didn't make sense to me. I tried solving for c like this: $n_0 = 1$ $2n^2 ≤ c * n^2 - 19n$ $2 ≤ c * (1-19)$ $2 ≤ c * -18$ $-36 \leq c$, but $c$ has to be a positive constant.
aryamank
  • 81
0
votes
1 answer

Using O-notation for asymptotic estimation of the number of additions in recursive function

Consider the following python program: def mystery(n): if n==0: return n * n return 2 * mystery(n//3) + 4 * n Let call the number of additions that are executed during the calculation a(n). How can I find an asymptotic estimation…
SlaMath
  • 73
0
votes
1 answer

Order the following three function of in increasing order of growth rate

I got this question wrong on my midterm, I need someone to explain how did they get the answer. $$ A(n) = \frac{2+3n}{5\sqrt{n}(1+4\log{n})} $$ $$ B(n) = \frac{2\sqrt{n}(4+7\log{n})}{\sqrt{n} + 5\log{n}} $$ $$ C(n) = 7\log{n} + 8^{(\frac{\log{n}}{9}…
user38543
  • 11
0
votes
1 answer

Which of these functions has the fastest asymptotic growth: $n^{1/3}\log_2(n)$ or $\frac{1}{4}(\log_2(n))^4$?

I can't seem to figure out which of the following functions has the fastest asymptotic growth: $n^{1/3}\log_2(n)$ or $\frac{1}{4}(\log_2(n))^4$? Can anyone show me with a proof?
Boris Grunwald
  • 431
0
votes
0 answers

How to find the Big-O of this function: $log(n!)/log(n)^3$

The definition of Big-O is $$u_n = O(v_n) \iff (\exists c \in \mathbb{R}^{*})\,\, (\exists N \in \mathbb{N}) \,\, n > N \implies u_n < c \, v_n$$ Based on that I am trying to find the upper bound for this function $log(n!)/log(n)^3$. What I've done…
HelloWorld
  • 1,564
0
votes
1 answer

big O with different orders

I'm trying to show the following and I'm not quite sure how: $f_1(n) = n^n$ is $O(f_2(n) = 3^{2^n})$ and $f_2(n) = 3^{2^n} = O(f_3(n) = 2^{3^n}) $ does anyone have an idea? calculating the limits is an option it's just that I don't get too far…
giorgioh
  • 322
0
votes
3 answers

Does big $\mathcal{O}$ imply $\Theta$

If we have a function $f(x) = 6x^4 - 2x^3 + 5$ and that function is $\mathcal{O}(x^4)$. Does that mean that it will also be $\Omega(x^4)$ and consequently $\Theta(x^4)$?
Michael Munta
  • 175
0
votes
2 answers

What is the asymptotic notation of a logarithmic function with a difference in exponents?

For example: $F(n) = \log(n) + 3\log^5(n^2) + 2\log^3(n)$ What would the asymptotic notation be since the logarithms have a different exponent. Are higher exponent logs more dominant in the notation?
Code4life
  • 9
  • 1
  • 4
0
votes
3 answers

Which function grows faster

Which function grows faster $f(n)=n^3$ or $g(n)=5^{\lg n}$ ?
Cookie cutter
  • 21
0
votes
1 answer

Prove that $n^2$ is $O(1.1^n)$

I am not sure with this example. Prove that $n^2$ is $O(1.1^n)$. Let $f(n) = n^2$ $g(n) = 1.1^n$ In other words, I need to find constant $c$ such that $f(n) = n^2 \leq c\cdot 1.1^n = c \cdot g(n)$. I start with $$g(n) = 1.1^n = (1+0.1)^n =…
Kapur
  • 489
0
votes
1 answer

Why subtraction of functions does not necessarily result in subtraction of their big O functions

How can I show that if $d(n)$ is $O(f(n))$ and $e(n)$ is $O(g(n))$, then $d(n) - e(n)$ is not necessarily $O(f(n) - g(n))$. Could someone explain it please?
k_shil
  • 103
0
votes
1 answer

Asymptotic expansion of $n(\sqrt[n]{a} - 1)$, if $a > 0$, to terms of $O\Big(\frac{1}{n^3}\Big)$

Asymptotic expansion of $n(\sqrt[n]{a} - 1)$, if $a > 0$, to terms of $O\Big(\dfrac{1}{n^3}\Big)$ Attempt: $n((1+(a-1))^\frac{1}{n} - 1) = n(1 + \frac{1}{n} a + \dfrac{\frac{1}{n}(\frac{1}{n}-1)}{2} a^2+ \cdots - 1)$ $n(\frac{1}{n} a +…
kayush
  • 2,441
0
votes
2 answers

Prove or disprove $f \in O(g)$, with $f=5^{\log(n)^2}$ and $g = n^{\log(n)}$

I have a feeling $f$ grows faster than $g$, and therefore it is not the case that $f \in O(g)$, but no matter how much I try, I do not see how to prove it. Any help?
Flavio Tisi
  • 11
0
votes
0 answers

How fast does the number of integer rectangles grow as a function of their area?

Suppose we define $R(k)$ as the number of $m \times n$ rectangles with integer sides and area $mn = k$ (we don't distinguish between $m \times n$ and $n \times m$). How fast does this function grow "on average" and "in the long run"?
Herman Tulleken
  • 3,608
1 2 3
…
74 75