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

$ n - \sqrt{n}$ $\Theta$ Complexity

$ n - \sqrt{n} \leq n - \sqrt{n} + \sqrt{n}=n=O(n)$ But I don't know what I should do about $\Omega(.) , \Theta(.)$ Should I try to solve it with lim?
Complex1238877
  • 153
0
votes
1 answer

comparing expressions confusion

This formula is actually from a big $O$ notation example, but I am confuse about the mathematical formula. I read that: if $n$ and $c$ are $1$, $3n^2 - 100n + 6$ is not a big o of $n^3$ or $cn^3 \lt 3n^2 - 100n + 6$ I'm confused here, if we…
user235991
  • 57
0
votes
1 answer

Asymptotic functions

Someone can help me to identify a function $f$ and a functon $g$ which statisfy the conditions specified below: $f(n) = \operatorname{O}(g²(n))$ $f(n) = \Omega(f(n)g(n))$ $f(n) = \Theta(g(n)) + \Omega(g²(n)))$ How is the approach to solve such a…
stone
  • 1
0
votes
1 answer

Understanding Asymptotic Notation of a constant

How can I prove that if $f(n) = O(1)$ leads to $f(n) = \Omega(1)$ as well? I need a Formal definition of the meaning that a function $f(n) = O(1)$
ThunderWiring
  • 141
0
votes
1 answer

What is this expression in big O notation?

$$2^{n-1} + 2^{n-1} + \ldots + 2$$ pretty basic question, but I'm afraid I don't know if it's $O(2^n)$ or $2^{O(n)}$
chibro2
  • 1,447
0
votes
1 answer

Where exactly is $n\log n$ between $n$ and $n^2$?

If I have $n^{1.161}$ and $n^{1.58}$, how do they compare in terms of time complexity relative to $n\log n$? I only know that $n\log n$ is between $n$ and $n^2$. I would probably factor out $n$ such that I will get $\log n$ vs $n^a$ where $0
maregor
  • 235
0
votes
1 answer

Growth rate of $n3^n$ vs $4^n$

Does the latter grow faster? I'm assuming that if we have $a^n$ vs $b^n$, if $b>a$ then $a = O(b)$, but if there is a n term in front of a does that change it?
maregor
  • 235
0
votes
1 answer

Is square root of n the same as log n for order notation of an algorithm

Given the context of a basic prime number testing algorithm that has the simple optimization of limiting the potential factors to the range from 2 to the square root of the subject number (instead of 2 to the number - 1) is it true that this…
Bohemian
  • 183
0
votes
1 answer

Prove that $\frac{f(n)+a}{g(n)+b} = O(\frac{f(n)}{g(n)})$

I was reading about algorithm analysis and I saw a similar simplification done in order to find the complexity. I became interested in proving that this simplification is formally correct but I am having trouble with the proof using the definition…
user1242967
  • 1,727
0
votes
1 answer

Floor function and little oh notation

Can we replace $o([x]^a)$ where $[x]$ is floor of $x$ and $a$ is a positive number with $o(x^{a})$? And can we replace $o(x^{a})$ with $o([x]^a)$?
MathPost
  • 1
  • 1
0
votes
1 answer

Asymptotic-Proof

I am looking at this questions and the proof for it and wondering how this works.Can anyone explain the answer to me or do you have any other way to answer this question.I am new to asymptotic notations $$2n^3 + 5n + 12 = O(n^3)$$ True Proof:…
user4203815
  • 95
0
votes
1 answer

Counting Primitive Operations

This is the solution I've been given for counting primitive Operation in an algorithm. I think I have my head around how all the operations are found, for instance the 2(n-1), the 2 is the primitive operations on that line and the n-1 is the amount…
JTK
  • 137
0
votes
0 answers

Question about big omega proof

I'm not sure if I should post it here or in StackOverflow, but anyway... Prove that: $n^5-2\log{n}=\Omega{(n^5)}$. Proof: We need to find $c, n_0 \geq0$ such that, for all $n \geq n_0$, $n^5-2\log{n} \geq cn^5$. $n^5-2\log{n}…
EMDB1
  • 477
  • 2
  • 8
0
votes
1 answer

Suppose that $f (x)$ is $O(g(x))$. Does it follow that $2^{f(x)}$ is $O(2^{g(x)})$?

Suppose that $f(x)$ is $O(g(x))$. Does it follow that ? First, I start from for some $c$ is a real number. Then, I find . But, if i start from , I just find . I confused with that different form.
james brown
  • 460
0
votes
0 answers

How to do this asymptotic task?

Let a(n) be the amount of natural numbers, which are smaller than n, and their prime divisors are only 2 and 3. For example: 6 is good, because it only has 2 and 3 has prime divisors, but 10 is not good because it has 5 as a prime divisor. 12 is…
Atvin
  • 3,392
1 2 3
…
74 75