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

Help on the derivation rules of the Big Theta notation

I'm really confused about the operation rules of the Big Theta notation. For example, I have met the following derivation process: $$ cos(\theta_r(y))=1+2(e^{-2y}+e^{-2r}-e^{R-r-y}-e^{-R-r-y})(1+\Theta(e^{-2r}))(1+\Theta(e^{-2y})) =…
crazyw0rld
  • 19
1
vote
2 answers

Big $\Theta$ arithmetic

I'm trying to understand this formula from this wikipedia article about amortized analysis. In general if we consider an arbitrary number of pushes n + 1 to an array of size n, we notice that push operations take constant time except for the last…
Hugh
  • 129
1
vote
3 answers

Big-Theta Notation. Is this theorem true?

Is the following sentence true assuming that $f$ and $g$ are differentiable and their derivatives are continous? I'd say yes, but don't know how to show it. $$g(x) \in \Theta(f(x)) \iff \frac{d}{dx} g(x) \in \Theta\left(\frac{d}{dx}f(x)\right)$$
Rob
  • 11
1
vote
1 answer

What are the “mild conditions” Wikipedia describes that allow asymptotic equivalence?

From “Asymptotic Analysis” on Wikipedia: If $f\sim g$ and $a\sim b$, then under some mild conditions, the following hold. $f^r\sim g^r$, for every real $r$ $\log(f)\sim\log(g)$ $f\times a\sim g\times b$ $f/a\sim g/b$ What are these “mild…
gen-ℤ ready to perish
  • 6,610
1
vote
1 answer

Using asymptotic definitions to prove or disprove statements

The statement I am trying to prove or disprove is $(2^n)^{1/3} \in \Theta (2n)$. I think this is false so I attempted to disprove it. Below is my proof (disproof). I want to make sure that a) I am correct in my thought that the initial statement is…
user65909
  • 65
1
vote
1 answer

Big-Oh notation asymptotic proof with faulty logic, trying to find the fault

What is wrong with this proof? According to the problem the claim of the proof is correct, but its not a sufficient proof. I'm a bit stumped on this one as to why it's not a valid proof, it seems so to me. I need to figure out where the issue is, I…
user65909
  • 65
1
vote
1 answer

Prove that $\lfloor\log_2n\rfloor$ is $\Theta(\log_2n)$

Having a little trouble getting started on this proof. Any advice on how to deal with this floor function is appreciated. Prove that $\lfloor\log_2n\rfloor$ is $\Theta(\log_2n)$. Here's what i have so far: By definition of $\Theta(g(n))$ we will…
River_B
  • 11
  • 2
1
vote
1 answer

Big Oh notation, some of my concerns about its definition

The formal definition of big $O$ notation we use is: "We write $f(x)=O(g(x))$ as $x\to x_0$, if there exists $A$ such that $|f(x)|\leq A|g(x)|$ in the neighbourhood of $x_0.$" So there are a few confusions/concerns of mine that I wanted to…
UnsinkableSam
  • 3,876
1
vote
0 answers

if $f(n)=\Theta (\Theta(g(n)))$, then $f(n)=\Theta g(n)$

Please correct me if I am wrong. Suppose $h(n)=\Theta (g(n))$ $f(n)=\Theta(\Theta (g(n)))$ $f(n)=O(\Theta (g(n)))$ and $f(n)=\Omega(\Theta (g(n)))$ $\exists c_1\in R(f(n)\leq c_1\theta(g(n))),\exists c_2\in R(f(n)\geq…
Andes Lam
  • 354
1
vote
0 answers

Big $O$: True or false statements

$f,g: \mathbb{N}_0 \rightarrow \mathbb{N}^+.$ $ f(n)^{O(g(n))}$ is the set of functions $h: \mathbb{N}_0 \rightarrow \mathbb{R}_0^+$ with $h(n) = f(n)^{k(n)}$ for a $k \in O(g).$ Explain whether these statements are true or false. a) $n + O(n) =…
franz3
  • 449
  • 3
  • 11
1
vote
2 answers

How can I analyze the asymptotic order of $n^{\ln n}$ and $(\ln n)^n$

I'm trying to analyze the asymptotic order of $n^{\ln n}$ and $(\ln n)^n$ At first, I take $\ln$ to both-hand-sides. So I got $(\ln n)^2$ and $n\ln(\ln n))$. However, I don't know what I should do next. Actually, my friends said, substitute $n =…
Jonghwan Hyeon
  • 193
  • 2
1
vote
3 answers

how to proof this big-oh statement?

I have a question on my homework which is: Prove that if $f(x)=O(g(x))$, and $g(x)=O(h(x))$, then $f(x) = O(h(x))$ I am not to sure how to prove this. This is my attempt. Is it good enough or am i missing something important? Thanks in…
Krimson
  • 591
1
vote
1 answer

Prove by induction: For $T(1)=1$, $T(n)=T(⌊\frac{n}{2}⌋)+T(⌈\frac{n}{2}⌉)+1=O(n)$

I only saw one problem involving induction so I am not sure what to do here. Here is what I tried and where I got stuck: For $n=1$, $T(1)=1\leq 1*1$, so we are covered. The hypothesis would be that for all $k
איתן לוי
  • 839
  • 4
  • 9
1
vote
3 answers

Question concerning big O

$\sum\limits_{i=1}^n(3i+2n)$ is $O(n^2)$ How do I solve this? I know that the answer for $\sum\limits_{i=1}^n(3i+2n)$ would be…
user1688953
  • 13
1
vote
1 answer

Asymptotic expansion to solution of $x - \log x = a$ for large $a$

Suppose $a \in \mathbb{R}$ is very large. Then there are two solutions to $x - \log x = a$. I was wondering what the asymptotic expansion of the larger solution to this equation is. The first term must be $a$ but what are the lower order terms?
user187437
  • 915
1 2 3
…
74 75