What can lead to the complexity of the O (log log n) algorithm?

Question

This earlier question describes some of the factors that can cause the complexity of the O (log n) algorithm.

What can lead to the fact that the algorithm has a time complexity of O (log log n)?

Answer 1

O (log log n) terms may appear in different places, but there are usually two main routes that will arrive in this runtime.

Square root reduction

As mentioned in the answer to a related question, the general way for the algorithm to have O (log n) time complexity is that this algorithm works by repeatedly reducing the input size down by some constant coefficient at each iteration. If so, the algorithm should end after iterations O (log n), because after performing O (log n) divisions by a constant, the algorithm should reduce the problem size to 0 or 1. That's why, for example, binary search has complexity O (log n).

Interestingly, there is a similar way to reduce the size of the problem, which gives the runtime of form O (log log n). Instead of halving the input at each level, what happens if we take the square root of the size at each level?

For example, take number 65 536. How many times must we divide this by 2 until we go down to 1? If we do, we get

• 65 536/2 = 32 768
• 32,768 / 2 = 16,384
• 16,384 / 2 = 8.192
• 8.192 / 2 = 4.096
• 4,096 / 2 = 2,048
• 2.048 / 2 = 1.024
• 1,024 / 2 = 512
• 512/2 = 256
• 256/2 = 128
• 128/2 = 64
• 64/2 = 32
• 32/2 = 16
• 16/2 = 8
• 8/2 = 4
• 4/2 = 2
• 2/2 = 1

This process takes 16 steps, as well as the case when 65536 = 2 ¹⁶ .

But, if we take the square root at each level, we get

• & radic; 65536 = 256
• & radic; 256 = 16
• & radic; 16 = 4
• & radic; 4 = 2

Please note that it takes only four steps to reach all the way to 2. Why is this? Well, let rewrite this sequence in terms of powers of two:

• & radic; 65.536 =? 2 ¹⁶ = (2 ¹⁶ ) ^1/2 = 2 ⁸ = 256
• & radic; 256 = & radic; 2 ⁸ = (2 ⁸ ) ^1/2 = 2 ⁴ = 16
• & radic; 16 = & radic; 2 ⁴ = (2 ⁴ ) ^1/2 = 2 ² = 4
• & radic; 4 = & radic; 2 ² = (2 ² ) ^1/2 = 2 ¹ = 2

Note that we followed the sequence 2 ¹⁶ → 2 ⁸ → 2 ⁴ → 2 ² → 2 ¹ . At each iteration, we reduce the exponent by two in half. This is interesting because it is related to what we already know - you can only divide the number k in half O (log k) times before it drops to zero.

So, take any number n and write it as n = 2 ^k . Each time you take the square root of n, you reduce the exponent in this equation. Therefore, there can only be O (log k) square roots applied before k drops to 1 or less (in this case, n drops to 2 or less). Since n = 2 ^k this means that k = log ₂ n, and therefore the number of square roots taken is O (log k) = O (log log n), therefore, if there is an algorithm that works by repeatedly reducing the problem to a subtask size, which is the square root of the original problem size, this algorithm will complete after steps O (log log n).

One real-world example of this is the van Emde Boas tree (vEB-tree) data structure. The vEB tree is a specialized data structure for storing integers in the range 0 ... N - 1. It works as follows: the root of the tree node has & radic; N pointers in it, dividing the range 0 .. N - 1 in & radic; N buckets, each of which contains a range of roughly radical N integers. Then these buckets are internally subdivided into & radic; (rad N) buckets, each of which contains roughly and the radius of (rad N) elements. To cross a tree, you start from the root, determine which bucket you belong to, and then recursively continue in the corresponding subtree. Due to how the vEB tree is structured, you can define in O (1) the time from which the subtree will descend, and therefore after steps O (log log N) you will reach the bottom of the tree. Accordingly, a search in the vEB tree takes only O (log log N) time.

Another example is the Hopcroft-Fortune nearest pair of points algorithm. This algorithm tries to find the two nearest points in a set of two-dimensional points. It works by creating a grid of buckets and distributing points into these buckets. If a bucket is found at any point in the algorithm that has more than & radic; N points in it, the algorithm recursively processes this bucket. Thus, the maximum recursion depth is O (log log n), and by analyzing the recursion tree it can be shown that each layer in the tree runs O (n). Therefore, the total execution time of the algorithm is O (n log log n).

O (log n) Algorithms for small inputs

There are other algorithms that achieve O (log log n) runtimes using algorithms such as binary search for objects of size O (log n). For example, the x-fast trie data structure performs a binary search on the layers in a tree of height O (log U), so the runtime for some of its operations is O (log log U). The associated y-fast trie gets some of its O (log log U) runtimes, maintaining balanced BST node addresses of O (log U) each, which allows searching in these trees to run in O (log log U) time. the tango tree and the associated multilayer trees of the O (log log n) data structure in their analyzes, because they support trees that contain O (log n) elements each.

Other examples

Other algorithms achieve O (log log n) runtime in other ways. An interpolation search expected that at runtime O (log log n) would find the number in the sorted array, but the analysis is quite in demand. Ultimately, the analysis works by showing that the number of iterations is equal to the number k, for which n ^{2 -k} & le; 2, for which log log n is the correct solution. Some algorithms, such as the MST Cheriton-Tarjan algorithm , arrive at runtime using O (log log n) by solving a complex problem with limited optimization.

Hope this helps!

Answer 2

One way to see the O (log log n) coefficient in time complexity is to divide as described in another answer, but there is another way to see this factor when we want to make a deal between time and space / time and approximation / time and hardness / ... algorithms, and we have some artificial iteration on our algorithm.

For example, SSSP (the shortest path with one source) has an O (n) algorithm on flat graphs, but before this complex algorithm there was a much simpler algorithm (but rather tough) with O (n log log n) runtime, the algorithm base is as follows ( just a very crude description, and I would suggest skipping the understanding of this part and reading the other part of the answer):

• divide the graph into pieces of size O (log n / (log log n)) with some restriction.
• Suppose that each of the mentioned parts of a node in a new graph G 'then calculates the SSSP for G' in time O (| G '| * log | G' |) ==> here, because | G '| = O (| G | * log log n / log n), we can see the factor (log log n).
• Calculate the SSSP for each part: again, because we have the O (| G '|) part, and we can calculate the SSSP for all parts in time | n / logn | * | log n / log logn * log (logn / log log n).
• update weights, this part can be performed in O (n). for more details this lecture is good.

But I want to say that we choose division by size O (log n / (log log n)). If we choose other divisions, such as O (log n / (log log n) ^ 2), which can work faster and brings a different result. I mean, in many cases (for example, in approximation algorithms or randomized algorithms or algorithms such as SSSP, as mentioned above), when we iterate over something (subtasks, possible solutions, ...), we choose the number of iterations corresponding to the trade of this we have (time / space / complexity of the algorithm / constant factor of the algorithm, ...). Perhaps we see more complex things than "log log n" in real working algorithms.