Is O (logn) always a tree?

Question

We always see that operations in the tree (binary search) have the worst running time O (logn) due to the height of the logn tree. I wonder if we will tell us that the algorithm has runtime as a function of logn, for example m + nlogn, can we conclude that it should include a (augmented) tree?

EDIT: Thanks to your comments, I now understand that divide-conquer and binary tree are so visually / conceptually similar. I never connected the connection between them. But I think about the case when O (logn) is not an algovy word in which there is a tree that does not have the property of the BST / AVL / red-black tree.

This data structure is disjoint sets with Find / Union operations, whose operating time is O (N + MlogN), where N is the number of elements and M is the number of Find operations.

Please let me know if I skip sth, but I cannot understand how the split game is going on here. I just see in this (disjoint set) the case that it has a tree without the BST property, and the runtime is the logN function. So my question is why / why I cannot generalize from this case.

Answer 1

What you have is exactly back. O(lg N) usually means some kind of division and conquest algorithm, and one common way to implement divide and conquer is a binary tree. While binary trees are an essential subset of all separation and quiescent algorithms, they are still a subset.

In some cases, you can directly convert other split and capture algorithms to binary trees (for example, comments on another answer have already made an attempt to claim that binary search is similar). However, for another obvious example, there is a multi-road tree (for example, tree B, tree B + or tree B *), and the tree is clearly not a binary tree.

Again, if you want strong enough, you can stretch the point that a multivariate tree can be represented as some kind of perverse version of a binary tree. If you want, you can probably stretch all exceptions to the point that they are all (at least something like) binary trees. However, at least for me everything that does is a “binary tree”, synonymous with “divide and conquer”. In other words, everything that you do nullifies your vocabulary and essentially erases a term that is both excellent and useful.

Answer 2

No, you can also binary search for a sorted array (for example). But don't take my word for http://en.wikipedia.org/wiki/Binary_search_algorithm

Answer 3

As an example of a counter:

 given array 'a' with length 'n' y = 0 for x = 0 to log(length(a)) y = y + 1 return y 

Runtime is O (log (n)), but there is no tree here!

Answer 4

The answer is no. Binary search for a sorted array O(log(n)) .

Answer 5

Logarithmic time algorithms are commonly found in binary tree operations.

Examples of O (logn):

• Search for an element in a sorted array with a binary search or balanced search tree.

• Look at the value in a sorted input array by dividing in half.

Answer 6

Since O (log (n)) is only the upper bound, all O (1) algorithms, such as function (a, b) return a+b; satisfy the condition.

But I have to agree that all Theta (log (n)) algorithms look like tree algorithms or, at least, can be abstracted to the tree.

Answer 7

Short answer:

Just because the algorithm has log (n) as part of its analysis does not mean that the tree is involved. For example, the following algorithm is very simple: O(log(n)

 for(int i = 1; i < n; i = i * 2) print "hello"; 

As you can see, the tree was not involved. John is also a good example of how a binary search can be performed on a sorted array. They take O (log (n)) time, and there are other code examples that can be created or specified. Therefore, do not make assumptions based on the asymptotic complexity of time; look at the code that you need to know for sure.

More about trees:

Just because the algorithm includes “trees” does not mean O(logn) . You need to know the type of tree and how the action affects the tree.

Some examples:

• Example 1)

Inserting or searching for the next unbalanced tree will be O(n) .

• Example 2)

An insert or search in the following balanced trees would be like O(log(n)) .

Balanced Binary Tree:

Balanced Tree Grade 3:

Additional comments

If the trees that you use do not have the ability to "balance", than there is a good chance that your operations will be O(n) time not O(logn) . If you use self-balancing trees, then inserts usually take longer, since balancing the trees usually occurs during the insert phase.