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

Big O: Prove that for all $x \leqslant y$, $n^x \in \mathcal O(n^y)$

For all real numbers, if $x \leqslant y, n^x \in \mathcal O(n^y)$. This is a homework question, so I'm just looking for a little guidance with this question, and not the answer. I understand how to prove Big O questions using actual functions, but…
user134796
  • 23
0
votes
1 answer

Asymptotic running time in Big Theta notation

If I have an algorithm with the running time $T(n) = 5n^4/100000 + n^3/100$, I know that I get Θ$(n^4)$. Now, if I have something like $T(n) = \frac{10n^2 + 20n^4 + 100n^3}{n^4}$, does this yield Θ$(n^3)$? I am trying to eliminate low-order terms…
manthemanman
  • 1
0
votes
1 answer

Equation with big O notation

Recently when I read a paper on Erdos's distinct distances problem, I met the following equation $$\dfrac{(mn-x)^2}{x}=O(m^{4/3}n^{4/3}+n^2)\quad\text{where $n\ge m$},$$ and the authors immediately got $$x=\Omega(\min\{m^{2/3}n^{2/3},m^2\}).$$ But…
Shane
  • 1,013
0
votes
2 answers

Big O, Omega and Theta Exercises

i have a few exercises to do but i need someone to correct me if they can. I am very new to the Big O notation so please forgive me for being too basic. I need to represent everything under Θ. T(n) = 10n + 2^(2*log n) --> Answer= Θ(n) T(n) = n^2.5 +…
Yann Bohbot
  • 13
0
votes
2 answers

Prove that $3^n=O(n^3) $ is not true

Prove that $3^n=O(n^3) $ is not true. I came up to $3^n \le cn^3 $ but can not go further, I guess I need to do log both side, But don't know
hacikho
  • 53
  • 7
0
votes
1 answer

Big O comparison

If $T(n) = \mathcal{O}(n^3)$ Then $T(n) = \mathcal{O}(n^2)$, is this statement right? Same question for omega, if $T(n) = \Omega(n)$ does that mean $T(n)= \Omega(n^2)$?
Lisa
  • 145
0
votes
2 answers

Quick Running Time Question

I have a quick question about some running time stuff. In my algorithm I run merge sort twice, then loop $n$ times. If this is the case, does this make sense? $\Theta(nlogn+nlogn+n) = \Theta(nlogn)$. I am a bit uncertain about the $\Theta(nlogn+n) =…
Matt
  • 33
0
votes
1 answer

Ordering Equations Using Small-oh Notation.

I have a couple questions about this problem: Order the following functions $h_i$, for $1 \leq i \leq 5$, with respect to relation $f \prec g$ defined by the small-oh notation as follows: $f \prec g \iff f = o(g)$. $$\begin{align*} h_1(n) &=…
datprog
  • 99
0
votes
1 answer

$d>0$ Prove $ d^n =O(n!)$

To solve this question , I came up below kinda solution: $ d^n $ $\leq n!$ $\frac{d^n}{n!} \leq$ constant But how am I prove this. By the way this is Big Oh Notation
hacikho
  • 53
  • 7
0
votes
2 answers

Why isn't $\log(n!) \leq O(n\log n)$?

Why isn't $\log(n!) \leq O(n\log n)$? I know that $\log(n!)$ is of $\Theta(n\log n)$ but why can't a function that is of $\Theta$ be $\leq$ than a function that is $O$ of the same parameter? Isn't every function that is $\Theta(n\log n)$ actually…
Georgey
  • 1,589
  • 2
  • 25
  • 39
0
votes
1 answer

Asymptotic Notations (Big Theta)

For an assignment, I have the following question: For all functions $\;f, g : \mathbb{N} \to \mathbb{R}^+$ from positive integer numbers to nonnegative real numbers, let the running time $T(n)$ of an algorithm be $\Theta(f(n))$, and $f(n)$ be a…
Marko
  • 1
0
votes
1 answer

Neglecting constants in big O notation

I'm just starting to learn big O notation and there's one thing in particular that bothers me. Say $f(n) = O(g(n)+c))$, where c is a constant. To my understanding, $f(n)$ can just be represented as $O(g(n))$ because constant terms don't really…
user3254763
  • 17
0
votes
2 answers

Finding tight bound for a function

Suppose we are given a rational function $f(n)=\frac{p(n)}{q(n)}$ and need to find g(n) that satisfies: $f(n) \in \Theta(g(n))$. Does g(n) need to be one of $n^c, log n, n log n$ or can it be, in this case $g(n)=f(n)=\frac{p(n)}{q(n)}?$
EggHead
  • 667
0
votes
2 answers

Are big-theta, Big-O, etc. all representative only of GROWTH of the function?

For example, $2^{n-1}$... is that $\Theta(2^n)$? it GROWS the same... but it in actuality will never be greater than or equal to the actual 2^n function, for example. $\log_2(n)$, is that $\Theta(\log_4(n))$? How do we handle growth of logarithm…
PinkElephantsOnParade
  • 317
0
votes
1 answer

Big-O problem, need help

f(n) = max(n^2, n^1.5 log^16 n) f(n) should be O(n^2),Omega(n^2), O(n^1.5 log^16 n)， or Omega(n^1.5 log^16 n)? Can anyone help me with it and explain why?
Mandy
  • 175
1 2 3
…
74 75