Tagged Questions

101 views

What does this $\asymp$ symbol mean? (subject: analytic number theory)

I'm reading a survey article by Andrew Granville on analytic number theory. On page 22 of the paper, there appears a strange looking symbol, undefined. I've circled it in red in the screenshot ...
39 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})$$
160 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 ...
39 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 ...
190 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.
41 views

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 ...
86 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 ...
96 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 ...
152 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 ...
52 views

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 ... 1answer 142 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)) ...
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 ...