[Solved]: What does tilde mean, in big-O notation?

Problem Detail: 

I'm reading a paper, and it says in its time complexity description that time complexity is $\tilde{O}(2^{2n})$.

I have searched the internet and wikipedia, but I can't find what this tilde signifies in big-O/Landau notation. In the paper itself I have also found no clue about this. What does $\tilde{O}(\cdot)$ mean?

Asked By : Johannes Schaub - litb

Answered By : manlio

It's a variant of the big-O that "ignores" logarithmic factors:

$$f(n) \in \widetilde O \left(h(n) \right)$$

is equivalent to:

$$ \exists k : f(n) \in O \left( h(n) log^k(h(n)) \right) $$

From wikipedia:

Essentially, it is big O notation, ignoring logarithmic factors because the growth-rate effects of some other super-logarithmic function indicate a growth-rate explosion for large-sized input parameters that is more important to predicting bad run-time performance than the finer-point effects contributed by the logarithmic-growth factor(s). This notation is often used to obviate the "nitpicking" within growth-rates that are stated as too tightly bounded for the matters at hand (since $log^k n$ is always $o(n^ε)$ for any constant $k$ and any $ε > 0$).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/63264

3.2K people like this

 Download Related Notes/Documents