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

How to extract $O(h^2)$ from $f\left(t_{i+1},y_i+hf(t_i,y_i)+O(h^2)\right)$

This is the formula of explicit Heun's method $$ y_{i+1}=y_i+hf\left(t_{i+1},y_i+hf(t_i,y_i)+O(h^2)\right)+O(h^3) $$ and I want to prove that this formula is $O(h^3)$.
Dante
  • 1,908
0
votes
1 answer

What is $\ O\left({n\over \left(\log \log n\right)^2}\right) $ equal or approximately equal to?

I already know big O notation and its use, but I can understand neither its value (or its approximation) in a "normal, ordinary" form (I'm referring to stuff like $\ n^2, 2n+1, 2^n $ etc.), nor whether it actually has one, and why shouldn't, since…
Vincenzo Oliva
  • 7,249
0
votes
1 answer

Big O evaluations

I'm confused about how to approach Big O problems. I'm presented two functions: $$f(n) = 4^{log_4n}$$ and $$g(n) = 2n +1$$ I simplified f(n) to: $$f(n) = n$$ Now I'm not sure how to compare f(n) and g(n). I tried looking at the ratio of…
Pandamonium
  • 975
0
votes
1 answer

Big Omega Notation

Using basic definition, we show that $n^2 - 10n = \Omega(n^2)$. For, $n \geq \frac{n}{2}$ for $n \geq 0$ $n – 10 \geq \frac{n}{2 \cdot 10}$ for $n \geq 10$ $n^2 - 10n \geq \frac{n^2 }{ 20}$ for $n \geq 10$ $ n^2 - 10n \geq c \cdot n^2$ for $n \geq…
JR Galia
  • 113
0
votes
1 answer

Confusion with Big-oh

So, big-oh means: for at least one choice of a constant k > 0, you can find a constant a such that the inequality f(x) < k g(x) holds for all x > a So let's evaluate the statement $1 = \mathcal{O}\log(n)$ We want to show that $1 < k \log(n)$. Now,…
Collin
  • 405
0
votes
1 answer

Show that $\int_{2}^x\frac{\pi(t)}{t(t-1)}dt=\log \log x+ O(1)$

Show that $\int_{2}^x\frac{\pi(t)}{t(t-1)}dt=\log \log x+ O(1)$ Do you use the fact that $\pi(t) = \frac{t}{\log t} + O\left(\frac{t}{\log^2t}\right)$ and then $\int_{2}^x\frac{\pi(t)}{t(t-1)}dt= \int_2^x\left(\frac{t}{\log t} +…
Pablo
  • 1,084
0
votes
2 answers

How to prove that $n^{1.1} \not\in O(n(\log n)^2)$

This is a problem from a university exam: True or false: $n^{1.1} \in O(n(\log n)^2)$. The solution says False, but I'm unable to prove it. I tried using the limit test for Big-O: $\lim_{n \to \infty} \frac{T(n)}{f(n)} = \lim_{n \to \infty}…
Frank Epps
  • 575
0
votes
2 answers

Determine whether the function floor(x) is big omega of x

I'm a little confused on what to answer to this: Determine whether the function floor(x) is big omega of x. The above function holds for integers but not for real numbers. According to the definition of big omega x could be either real or integer so…
TuSe
  • 3
0
votes
1 answer

Asymptotic notation problems, am i correct??

$f(n)$ belongs to $\Theta(g(n))$ then it implies that $2^{f(n)}$ belongs to $\Theta(2^{g(n)})$. [True] $f(n)$ does not belong to $o(g(n))$ and $f(n)$ does not belong to $\omega(g(n))$ then it implies that $f(n)$ belongs to $\Theta(g(n))$-…
girl101
  • 333
0
votes
1 answer

Check if $f(n)+g(n)=O(\min \{ f(n), g(n) \})$

Let $f(n)$ and $g(n)$ be asymptotically positive functions. I want to check if $f(n)+g(n)=O(\min \{ f(n), g(n) \})$. That's what I have tried: Let $f(n)+g(n)=O(\min \{ f(n), g(n) \})$. Then, $\exists c>0 , \exists n_0 \geq 1 \text{ such that }…
evinda
  • 7,823
0
votes
1 answer

Are these asymptotic inequalities identical?

I'm struggling with asymptotic notation a little bit... As $k$ becomes large, are these two inequalities actually the same? $k \le n^{\log (n+1) - 1}(1+o(1))$ and $k \le n^{\log (n)}(1+o(1))$? the first one is better, but it makes no difference…
user163833
  • 9
0
votes
1 answer

Can we say that $ 2^\frac{n}{\log(n)} \sim 2^\frac{\log(n)}{\log(\log(n))}$?

Can we assert and proove that : $$ 2^\frac{n}{\log(n)} \sim 2^\frac{\log(n)}{\log(\log(n))}$$ And What inequality relating two parts can be proved ?
Naoufal EL JAOUHARI
  • 187
0
votes
2 answers

Big O notation $a*n + b = O(n^2)$

According to the book "Introduction to Algorithms" a function that has the following form$f(n)=an+b$belong to $O(n^2)$ , and that this can be easily proven if we set$c = a +|b|$ But I don't get it, it still seems to belong to $O(n)$.
QxFFu
  • 45
  • 1
  • 1
  • 4
0
votes
1 answer

Asymptotics of two functions

Is $$O(1-cf(n))=O(1-f(n))$$ for any constant $c$ and any function $f$? I am afraid not. Could you tell me how to get from $$1-cf(n)$$ to $$1-f(n)?$$ Anything I can think of is $$1-cf(n)=c(1-f(n))+1-c=O(1-f(n))+1-c$$ but this does not help.
user136457
  • 2,560
  • 1
  • 22
  • 41
0
votes
1 answer

Which one of the following is greater?

Hi I am studying Asymptotic analysis but generally find difficulty in identifying the greater of two functions ? Like ex. $$f(n) = ((n^2)(\log_2(n))\\ g(n) = n((\log_2(n))^{10})$$ (here log are to base 2). So, I know log to base 2 means $\log…
Kunal
  • 1
1 2 3
…
74 75