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

105 Views Asked by At

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 it is used in equalities and inequalities too. As long as it deals with approximation, I also thought that $\ O(n) $ might mean $\ \approx n\ $ or $\ \sim n $, but I guess it's not like that.

P.S. Yes, actually I've never studied this, I'm approaching it on my own, and without any truly sufficient basis. But I'd like to understand anyway.

1

There are 1 best solutions below

0
On BEST ANSWER

Short answer: $$O\left({n\over (\log \log n )^2}\right) = O(n)$$

Long answer:

The point of big $O$ notation is about algorithmic complexity for tasks that will have a very large number of steps. It's only the order that matters, so you would not ever see something like $O(2n+1)$, you would just have $O(n)$, instead.

For example, say you have a list of 1 million personnel records, sorted by name (last, first).

  1. Finding a particular record, based on name would take $O(\log_2 n) = 20$ steps. You'd start at the middle record. If that isn't the one you seek, you would next search the half above or below, based on the comparison. Starting with the middle each time, the search would require about 20 comparisons.

  2. Find a particular record, based on id number. The list is not sorted by id number, so you'd have to check every record. On average, you would have to search half the records, or 500,000. This is $O(n)$.

  3. Sort the list by id number, using an efficient algorithm, like Quicksort. This algorithm is optimized and would require, on average, about 20 million comparisons. This is $O(n \log_2 n)$.

  4. Sort the list using bubble-sort. This will, on average, take 500 billion comparisons. This is $O(n^2)$.

  5. Examine all the possible groupings of people on this list. There are $2^{1000000}$ combinations, which is a number about 300 thousand digits long. This is $O(2^n)$.

  6. Sort the list using an algorithm that simply cycles through all the possible permutations until it finds the correct one. This would take about 1000000! steps, which is a number 5 million digits long. This is $O(n!)$.

Each step above, from 20 to 500 thousand to 20 million to 500 billion, etc., is a quantum leap of complexity. A factor of two is small compared to the order. The interest in big $O$ notation is that it can tell you whether using a particular approach is feasible.

In general for large lists, $O(n^2)$ is impractical except for rare occasions (monthly reports, for example), while anything larger than that will always be impractical. For example, the permutation-sort (example 6, $O(n!)$) becomes impractical before $n$ reaches 20.

Even for very large $n$, $\log(\log(n))$ is essentially a constant. $$\log_2 \log_2 20 = 2$$ $$\log_2\log_2 10^6 = 4$$ $$\log_2\log_2 10^{100} = 8$$

Practically speaking, the difference between an algorithm that was $O(n)$ and one that was $O\left({n/(\log \log n)^2}\right)$ is negligible. Implementation details will be more important.