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

Why asymptotic notation trying to get rid off multiplicative constants?

When I reading through an article about asymptotic notation, there is a sentence - "For large enough inputs, the multiplicative constants and lower-order terms of an exact running time are dominated by the effects of the input size itself." I get…
wintop6211
  • 103
0
votes
1 answer

Is there a product rule for Big-Omega?

I came upon the need to multiply two function run-times: $\Omega(f)*\Omega(g)$. On wikipedia, such product exists for Big-Oh notation (and equals $O(f*g)$), but the $\Omega$ page is very lacking. I couldn't find anywhere online (including…
yoad w
  • 151
0
votes
1 answer

Asymptotic expression for $\left(\frac{1}{\varepsilon}\right)^{\cfrac{1}{1-\varepsilon}}$

My question is regarding the expression below, where $\varepsilon\ll1$. $$\left(\frac{1}{\varepsilon}\right)^{\cfrac{1}{1-\varepsilon}}$$ Is it possible to express this in the…
Freeman
  • 5,399
0
votes
1 answer

Proving that $2^{2n}-n^2+3^n = \Omega (2^{2n})$

I need to prove that: $2^{2n}-n^2+3^n = \Omega (2^{2n})$ I started and got to this: $2^{2n}-n^2+3^n \geq 2^{2n}\cdot 3 \geq 2^{2n}\cdot 2 = 2^{2n+1}$ for every $n > n_{0} = 1$ How should I continue from here?
Lisa
  • 21
0
votes
1 answer

Lower bound on binomial coefficient

Prove that $\binom{n}{k} ≥ \left(\frac{n}{k}\right)^k$ for integers $0
nn123
0
votes
1 answer

How to calculate $O(\sum_{k=1}^{K}(N-k)(k+1)^2)$?

Using the formula for the sum of the squares and the sum of first $K$ numbers I can get that: $$\sum_{k=1}^{K}(N-k)(k+1)^2=\dfrac{1}{12}K(-3K^2+2K^2(2N-7)+3K(6N-7)+26N-10)$$ Now I guess I can simplify the formula if I would like to get the big-O. I…
zebda
  • 39
0
votes
1 answer

Big O notation where C is negative

How do you prove the following? What I have so far:
raul
  • 101
0
votes
1 answer

How to prove/disprove Big $\Theta$

I would like to prove or disprove $$4^n = \Theta(2^n)$$ I think you may have to simplify the $4^n$ to $2^n*2^n$ but am unsure where to go from there. Any idea? Thank you
user318799
  • 9
0
votes
0 answers

Big O, Omega and Theta Notation Properties

As an exercise, we have to prove or disprove certain statements about the properties of Big O Notation. I struggle with two of those right now. "For all $a,b \in N, a \le b: n^{\frac{1}{a}} \in \Theta(n^{\frac{1}{b}})$." Is the first one correct?…
Seen
  • 145
0
votes
1 answer

How to get values of $n_0$ and $c$ for big-omega.

Let $f(n)=3n^3$ and $g(n) = n^3$ then $f = Ω(g)$ Answer: Let $n_0 = 0$ and $c = 1$ So I know how to find $c$ and $n_0$ for big-oh, like this: $3n^3 \leq cn^3$ [divide to be left with c] $= c = 3$ and then $n_0 = 0$ I am not sure how to relate…
karambit
  • 171
  • 5
  • 17
0
votes
2 answers

Prove or disprove that $\forall n \in N$ $, \, n! \in \mathcal{O}(2^n)$

Prove or disprove that $\forall n \in N$ $, \, n! \in \mathcal{O}(2^n)$ My attempt: $f(n) = n!$ $g(n) = 2^n$ First I checked if I needed to prove or disprove this statement, and to do so I computed the $\lim_{n \to \infty}{\frac{f(n)}{g(n)}}$ =…
user3412839
  • 475
0
votes
1 answer

Asymptotic behavior of two functions

I have trouble figuring out the asymptotic behavior of two functions. If $f(n) = n \log n$, then what do we know about $f^{-1}(n)$? I.e. what is the asymptotic behavior of $g(n)$ such that $g(n) \log(g(n)) = \Theta(n)$, perhaps in terms of some…
taninamdar
  • 2,618
  • 14
  • 24
0
votes
2 answers

find the asymptotic upper bound

I need to find the asymptotic upper bounds in $O$ notation for $T(N)$ in two recurrences. Assuming that $T(N)$ is constant for sufficiently small $N$, I need to make the bounds as tight as possible. $T(N) = T(N-3) + 3 \log N$ $T(N) = 2T(N/4) +…
crazyGracie
  • 23
0
votes
2 answers

Prove or Disprove Θ

I want to prove or disprove that $3n^3 +n^2\log(n) = Θ(n^3)$. I'm aware that I will need to either prove or disprove both big-o and big-Ω to prove or disprove Θ. I am simply struggling to do so. Help appreciated.
crazyGracie
  • 23
0
votes
0 answers

Big-Theta - asymptotic bound - is solution sufficient enough?

I am wondering is my solution sufficient enough (or detailed enough) for the following question? or it is even a valid solution? Question: Find a tight asymptotic bound ($\Theta$) in terms of the following code segment, where $n \ge 1$ is an…
Node.JS
  • 1,119
1 2 3
…
74 75