0
votes
0answers
38 views

Meaning of theta notation in summation.

Just a simple question: What does the big theta notation mean in this equation? $$S(n,p) = \sum_i^ni^p=\Theta(n^{p+1})$$
1
vote
3answers
113 views

Equation with the big O notation

How I can prove equality below? $$ \frac{1}{1 + O(n^{-1})} = 1 + O({n^{-1}}), $$ where $n \in \mathbb{N}$ and we are considering situation when $n \to \infty$. It is clearly that it is true. But I ...
0
votes
3answers
34 views

What is the correct notation for simplifying O notation?

For instance I want to say something like: "Here is the resulting runtime: $$\sum_{x}^{n}\sum_{y}^{x} (1) = \frac{n(n+1)}{2} \implies n^2 \implies O(n^2)$$" But what is the proper way to state this ...
1
vote
5answers
152 views

What does this symbol “$\gg$” mean

I was reading a paper and came to a symbol as follows: "$\gg$" (e.g. $x\gg 5$). What does that mean? Is it larger than or has more information to mention? Thanks.
0
votes
0answers
31 views

Question about Big-Omega notation

I've leared that BigOmega is the lower bound of a function (or, can be used to describe that). The counter to Big-O's upper bound. Does this mean, say 3n^2 - 2n is BigOmega(n), as well as ...
0
votes
0answers
65 views

Big O notation - time complexity of an algorithm - relation between functions

Let's say I have an algorithm whose time complexity is $f=O(nB)$. But we ask for time complexity of algorithm with respect to the number of bits required to represent the input, and the function of ...
0
votes
1answer
50 views

Time complexity in terms of theta notation [duplicate]

sum= 0; for (i = n; i > o; i = i/3) for (j = 0; j < n^3; j++) sum++; what is the time complexity (in Θ- notation) in terms of n? so far, i've gotten to this point: The ...
-1
votes
1answer
91 views

Time complexity function in terms of theta notation

sum = 0; for (i = 0; i < n; i++) for (j = 1; j < n^3; j = 3*j) sum++; what is the time complexity (in $\Theta$-notation) in terms of ...
1
vote
1answer
42 views

Nesting big-O with big-Omega $O(g(\Omega(h(n))))$: is it $O$ for all $\Omega$ or for one $\Omega$?

I want to express the following statement about a function $f(n)$: there exists $f_\Omega\in\Omega(h(n))$ such that $f\in O(g(f_\Omega(n))$. What's the correct notation for this? Is it $f\in ...
0
votes
1answer
118 views

Asymptotic notation meaning in transitive relation

I'm attempting to prove the transitive relation on $\theta$ and I'm having trouble understanding the meaning of one of the symbols used. Here is the transitive relation: $f(n) = \theta(g(n)) ...
1
vote
1answer
25 views

Asymptotic Approximation and Sign Convention

When I write the asymptotic approximation of a function, does the sign convention matter? i.e. suppose I have (though the formula might not make sense) $$f_n(x)=x^2+\dots-O(n),$$ If my function is ...
1
vote
1answer
36 views

Mixing asymptotic notations

I have a function $f(x) = g(x) - h(x)$ and I know that $g(x)=\Omega(\hat g(x))$ and $h(x)=O(\hat h(x))$. Is it well-defined to express this in asymptotic notation, as $f(x) = \Omega(\hat g(x))-O(\hat ...
2
votes
2answers
35 views

Nesting of different Asymptotic operators

Is it possible to nest big-oh notation with omega-notation? I came across this here, while doing calculations on an exercise: $$ f(x) \in O(\Omega(\log x)) $$ I'm really unsure on how to properly ...
2
votes
1answer
259 views

Big O notation: relation between Omega and Big O?

Can I do this if I need to proove something for $\Omega$: $f(n) \in \Omega(g(n)) \iff g(n) \in O(f(n))$?
5
votes
3answers
222 views

“$O$” notation in Stirling approximation

In the Stirling approximation the formula as typically used in applications is $$\ln n! = n\ln n - n +O(\ln(n))$$ I'm confused about the last term "$O$" . What does it mean actually, and when do we ...
4
votes
1answer
74 views

Asymptotic value in math.

What does the term $o(k^2)$ in $f(k)=k^2/2+o(k^2)$ mean ? I have used the asymptotic notation only in context of algorithmic complexity. With an analogy that, I am guessing it says $f(k)$ returns ...
3
votes
1answer
223 views

Are there straightforward methods to tell which function has fastest asymptotic growth without a calculator?

For example, suppose I wanted to determine which of the following has the fastest asymptotic growth: $n^2\log(n)+(\log(n))^2$ $n^2+\log(2^n)+1$ $(n+1)^3+(n-1)^3$ $(n+\log(n))^22^{100}$ Are there ...
0
votes
2answers
932 views

Big O Notation and finding witnesses

I am trying to figure out some stuff here with Big O Notation. I mean I understand the concept of it and can generally be able to tell what the efficiency of something is, but I do not really ...
1
vote
1answer
169 views

little o notation with natural logs

I'm having trouble with little o notation. Help me show that: $2(n^2 + 100n)\log^5n = o(n^2\sqrt{n})$. It is the last hwk on my sheet and I don't understand it, if someone can help me with ...
2
votes
3answers
308 views

big O notation with asymptotically nonnegative increasing functions

Let $f(n)$ and $g(n)$ be asymptotically nonnegative increasing functions. Show: $f(n) · g(n) = O((\max\{f(n), g(n)\})^2)$, using the definition of big-oh. I can't quite figure this out, can ...
4
votes
2answers
296 views

Big Oh notation Question in calculus

In my text book, they state the following: $$\begin{align*}f(x) &= (\frac{1}{x} + \frac{1}{2}) (x-\frac{1}{2}x^2+\frac{1}{3}x^3+O(x^4))-1& ,x \rightarrow 0\\&= ...
1
vote
2answers
176 views

expressing $x^3 /1000 - 100x^2 - 100x + 3$ in big theta

Hello can somebody help me in expressing $x^3/1000 - 100x^2 - 100x + 3$ in big theta notation. It looks like of $x^3$ to me, but obviously at $x =0$ obviously this polynomial gives a value of $3$. And ...
3
votes
1answer
291 views

Disproving a big O equation

As a homework assignment I am trying to prove/disprove the next statement: Let $f(x)=O_a(g(x))$, then $\forall A,B\in\mathbb{R}\rightarrow A\cdot f(x)=O_a(B \cdot g(x))$ Which I think is wrong ...
1
vote
2answers
221 views

Particular Use of Big O Notation

I'm reading a theorem that states "...Then for each $j$ and $\epsilon>0$, there exists $n\leq 2^{O(j/\epsilon)}$..." What exactly is the big-oh notation saying in this case? I guess it must be ...
1
vote
2answers
283 views

How to interpret the little-$o$ notation in this definition of the Poisson process?

In the book Probability and Random Processes by Grimmett and Stirzaker, a Poisson process is defined to be any process $(N(t))_{t\in[0,\infty)}$ with values in $\mathbb{N}_0$ satisfying following ...
1
vote
1answer
80 views

Notation for asymptotic bounds with coefficients?

I ran into the following notation issue: Suppose that I have two functions $f$ and $g$ and I know that $\displaystyle \lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} = c$ for some $1 < c < ...
23
votes
2answers
1k views

What are the rules for equals signs with big-O and little-o?

This question is about asymptotic notation in general. For simplicity I will use examples about big-O notation for function growth as $n\to\infty$ (seen in algorithmic complexity), but the issues that ...
4
votes
3answers
505 views

Proving that $2n^2+3n+1=O(n^2)$

For Big-O notation in mathematics, How does $f(n) = 2n^2 + 3n + 1 = O(n^2)$? Does it require any more information for the proof? Edit: ...
0
votes
1answer
125 views

Does $f \sim g$ imply $f \asymp g$ in certain conditions?

I got a good answer to this question over on MathOverflow a while ago. Harald Hanche-Olsen claimed that, if $f, g: D\to \mathbb{R}^+$, then $$ f(x) \sim g(x) \implies f(x) \asymp g(x) \qquad \qquad ...
3
votes
1answer
686 views

Determine if function is little-o, little-omega or big-theta

Let $f(n) = n^3(5+2\cos(2n))$ and $g(n) = 3n^2+4n^3+5n$. Given these two functions, I must determine the appropriate symbol where the underscore is: $f(n) \in \_(g(n))$ So, first thing to do is take ...
0
votes
1answer
221 views

Notation: What does $f(x) = x^{-\omega(1)}$ mean?

I am reading a cryptography paper, and the authors introduce a function $f(x) = x^{-\omega(1)}$ and call it a negligible function in $x$. What is the possible meaning of this?