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

Tangent Approximation

Today I saw the approximation $\tan(2 \theta) \approx 2\tan(\theta)$ when $\theta$ is small. I justified this by seeing that these two functions have the same linear taylor expansion about $\theta = 0$. Is there a direct way to go from one to the…
countunique
  • 2,449
0
votes
2 answers

f(n)∈O(g(n)) ∧ g(n)∈O(f(n))

I have a little question about giving an example for functions that fullfil the condition f(n)∈O(g(n)) ∧ g(n)∈O(f(n)) . From what I know, or think to know: First half of it means that f(n) ≤ c*g(n) and the same for the second half, just visa…
Progressive
  • 3
0
votes
3 answers

Asymptotic notation (big O)

Asymptotic notations are a little vague for me at the moment. Here I have a problem that asks me if two equations are equal to each other, and it involves the big O notation. I wrote my question in the image in magenta color.
Conrado Sanchez
  • 61
0
votes
1 answer

Example of Little-oh

The question is: A simple example of a function that is $o(n)$ is $\ln(n)$. Give another example of a non-negative, non-constant function that is $o(n)$. I thought about using $f(n) = 10n - n\ln(n)$ but I am not sure if it's a good enough answer…
CSstudent
  • 23
  • 3
0
votes
2 answers

Proving Big O and Theta notations of functions are in the subset of Big O

HOMEWORK QUESTION Prove that Θ(n) + O(n^2) ⊆ O(n^2). Note that for this problem, you are proving that the set of functions on the left hand side (LHS) is a subset of the set of functions on the right hand side (RHS). The set on the LHS is the…
Eli
  • 1
  • 1
0
votes
1 answer

How to prove that $n^{3.14}−2017n^{1.28}+1 \in ω(n^3)$ without using limit

How to prove that $n^{3.14}−2017n^{1.28}+1 \in ω(n^3)$ without using limit?
Barbara
  • 1
0
votes
1 answer

What does it mean that a big-oh notation is not total order?

Before asking this question, I tried checked many sources on the internet but couldn't find an answer for my question. What does it mean that a notation has a total order ? For example, if we have f(n) = ϴ g(n), that includes g(n) = ϴ f(n) which…
Zok
  • 209
  • 1
  • 8
0
votes
1 answer

Wording Big-O notation estimates

Please could someone advise on my solution to the following problem. Am I wording this right or could you offer a better way? Question is to show that $S_n =O(n^3)$ where $S_n = \sum_{k=1}^n(k^2)$ Solution: $$\begin{align*}S_n &= n(a_1 + a_n)/ 2…
bosra
  • 561
0
votes
1 answer

What is number of comparision here?

I'm getting answer floor $(log_ 2 n) +2$ ? I m wrong or what is right answer. This is GATE exam question.
sittian
  • 63
  • 2
  • 10
0
votes
2 answers

Asymptotic notation

Which of the following is false? A) $100n \log{n}=\left(\frac{n \log{n}}{100}\right)$ B) $\sqrt{\log{n}}=O(\log \log{n})$ C) If $0
sittian
  • 63
  • 2
  • 10
0
votes
0 answers

asymptotic of Riemann xi function on the critical line

given the Xi function on the critical line $ \xi ( 1/2+iz) $ then for big $ z \to \infty $ would be the following asymptotic be valid ? $$ \xi( 1/2+iz) \sim g(z) $$ where $ g(x)$ is a real function with real roots and the roots of 'g' satify the…
Jose Garcia
  • 8,506
0
votes
1 answer

Using the definition of Big-Theta to prove a theorem.

If $f(n) \in \Theta(n)$ and $g(n) \in \Theta(n)$, then $f(n) + g(n) \in \Theta(n)$ I'm supposed to prove the following theorem below using the definition of $\Theta(n)$. I know the definition of Big-Theta, but I don't understand how to use it prove…
Jasmine
  • 67
0
votes
1 answer

Prove that for all constants $a, b>1$, $\log_a{n}$ is $\Theta(\log_b{n})$

So far I have established that I should be showing the following relationship: $k_{1}$ $\leq\ \frac{\log_a{n}}{\log_b{n}} \leq\ k_{2}$ where $k_{1}, k_{2}$ $>$ 0 but I'm not sure how to go about this. Any ideas?
user402081
  • 3
0
votes
0 answers

$\Omega$ definition

Assuming that $g$ is eventually positive, then $f = O(g)$ means that $|f(x)| \le cg(x)$ for some positive constant $c$ and all sufficiently large $x$; $f = \Omega(g)$ means that $ f(x) \ge cg(x)$ for some positive constant $c$ and all sufficiently…
chen
  • 133
0
votes
1 answer

Big O notation meaning

Geometric meaning of $O(1)$? Need $O(1)$ maps $0$ to $0$? The definition of big O notation is clear for me.But such questions i could not understand. By definition $O(1)$ is any mapping which is bounded.For example $f(x)=O(1)$ as $x\to x_0$ means…
Jamal Gadirov
  • 205
1 2 3
…
74 75