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

My proof that $T(n) = 2T(n/2) + n$ is $\Omega(n \lg n)$

My proof that $T(n) = 2T(n/2) + n$ is $\Omega(n \lg n)$: Assume $T(m) \geq cm \lg m$ for $m < n$. $T(n) \geq cn \lg(n/2) + n = cn \lg n - cn + n \geq cn \lg n$, for $0 < c \leq 1$. Since we just have to find there exists a positive constant c,…
Dak Song
  • 151
0
votes
2 answers

Proving little o by first principles

I'm trying to prove that $15n+7$ is $o(n\log n)$ (by first principles, i.e. no limits). My idea is to solve for n to determine $n_0$ and then work backwards from there. But I can't seem to find a way. $15n+7 < cn\log n$ $7 < n(c\log n-15)$ I got…
Pierre
  • 147
0
votes
1 answer

My proof of "Is $2^{2n} = O(2^n)$?"

I was wondering if my proof for this problem was correct. Let $x = 2^n$. Then the problem reduces to is $x^2 = O(x)$, which is clearly false.
Dak Song
  • 151
0
votes
2 answers

Asymptotic Analysis of same-degree functions

On a recent test, I was asked whether the following is true or false: True or False: $10n^3 = O \left( 0.42n^3 \right)$ Comparing the two functions as n approaches infinity, I get: $ \lim_{n \to \infty} \frac{10n^3}{0.42n^3} = \frac{10}{0.42}…
StudentsTea
  • 2,218
0
votes
3 answers

Proving that $h=O(\log_2 n)$ if $h=\log_2 (n+1)$

Suppose that $h=\log_2 (n+1)$. Why is $h$ also $O(\log_2 n)$? I know the definition of big $O$ notation, and properties or logarithms, but I can't figure it out - that $+1$ is causing troubles.
user4205580
  • 2,083
0
votes
1 answer

asymptotic notations : if $0

If $0
Ancient Dragon
  • 21
0
votes
1 answer

Which one grows faster?

Is the following statement true or false? $(\log n)^{10} = O(n^{0.10})$ When trying to solve this, I thought it was false, but according to my teacher's answers, it's true. I would like to know if there is a quick and easy way to solve exercises…
Jesper
  • 121
0
votes
2 answers

Find the asymptotics of $n(\frac{n-1}{n})^n$

Find the asymptotics of $n(\frac{n-1}{n})^n$. I know $f(x)$~ $g(x) $ if $lim\frac{f(x)}{g(x)}=1$ but I am unsure as to how I found $g(x)$ I found a solution $\frac{2n-1}{2e}$ but I am unsure where that comes from Any help would be appreciated Thanks
MCCR
  • 31
0
votes
1 answer

Determine asymptotic complexity of the code

I need to determine asymptotic complexive. PROGRAM(A,n,x): begin l:=0 r:=n-1 while TRUE do while l=x do r:=r-1 end if l>=r…
user4362081
  • 93
0
votes
1 answer

Big O Notation asymptotic relationship

I cannot prove correctness/incorrectness of the implication of two functions f(n) and g(n) in Big-Oh/asymptotic notation $$g(n) = \Omega(f(n)) ) \implies g(n) = O(n^2f(n))$$ I believe $g(n) = \Omega(f(n)) ) \implies f(n) = O(g(n))$ but not the other…
HGO HGO
  • 57
0
votes
1 answer

Which one is asymptotically larger?

The question is to find out which among $n^\sqrt{n}$ or $n^(log_2 n)$ is asymptotically larger? Now as a solution I read somewhere that if we take log on both sides and then compute which one is larger, it gives the same result. Like, taking log…
bandit_king28
  • 403
0
votes
1 answer

The Big O Notation and the Thetha Notation

I was instructed to find whether $$x*⌈x⌉*⌊x⌋$$ is$$ O(x^3) $$ or $$Big Thetha(x^3)$$ I tried to do a solution by cases, and i got : if x is not an integer, $$x=b+є$$ $$⌈x⌉=b+1$$ $$⌊x⌋=b$$ Then $$x*⌈x⌉*⌊x⌋=(b+1)(b)(b+є)$$ If x is an integer , then…
Jack
  • 107
0
votes
0 answers

Big O notation question (conceptual)

In my class, we have defined that $$ f(x) \ll g(x) $$ on $A$ if there exist a strictly positive c such that $$ |f(x)| \le cg(x) $$ for every $x$ on $A$. I'm a bit confused. Say that $ f(x) = x$ and $ g(x) = \frac x2 $ We could take $c = 3$, and…
math7dg7
  • 3
0
votes
1 answer

Proving equation using formal O(f(n)) - step by step?

I have huge problems showing whether example like this: is true or false using formal definition of Big O. How can I solve such problems step by step? I understand that formal definition of O(f(n)) is "for any n ≥ n0, f(n) ≤ cg(n)". What does it…
qwerty
  • 147
0
votes
1 answer

How to show that $f_2(n)=2^n$ grows faster than $f_1(n)=n^{\log{n}}$

The graphs of the two functions $f_1(n)=n^{\log{n}}$ and $f_2(n)=2^n$ clearly show that $f_2$ grows faster than $f_1$, but how do we mathematically prove this?
acheigrec
  • 11
1 2 3
…
74 75