Complexity and binary tries

Question

I have a big problem understanding complexity and especially with binary trees.

For example, I know that when we have a problem, with say the problem's size is x=log2(sizeofarray) but I don't understand where this log2 comes from?

score 1 · Answer 1 · edited May 23 '17 at 11:45

1

It's log₂ because each level of tree splits your problem into two.

For instance, consider this set of data:

{ 1, 2, 3, 4, 5, 6, 7, 8 }

The first level could be

{ 1, 2, 3, 4 }, { 5, 6, 7, 8 }

the second level:

{ 1, 2 }, { 3, 4 }, { 5, 6 }, { 7, 8 }

the third level:

{ 1 }, { 2 }, { 3 }, { 4 }, { 5 }, { 6 }, { 7 }, { 8 }

Here with 8 values, log₂(8) = 3, and there are 3 levels in the tree.

Also see these other StackOverflow questions for more:

"Why is the height of a balanced binary tree log(n)? (Proof)" - the answer follows a similar vein to the answer that Amadan posted on this question.
"Search times for binary search tree" - contains some pretty ASCII art, and examines best/worst case scenarios.

edited May 23 '17 at 11:45

Community

1
1

answered Apr 24 '15 at 06:45

Wai Ha Lee

8,598
83
57
92

thank you, and what about this best / worst case scenario? could we say that if the element we're searching is at the total bottom the comlexity is log2(size) and if it's at the top it's O(1) ? – pengj Apr 24 '15 at 06:50
1

worst case is you have to travel through the *whole* tree, that gives you a complexity of O(size) where size is the number of nodes in the tree, no log in that case – user2314737 Apr 24 '15 at 07:02
As @user2314737 correctly points out, the worst case is a is a [degenerate tree](http://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees), which is basically a [linked list](http://en.wikipedia.org/wiki/Linked_list). – Wai Ha Lee Apr 24 '15 at 07:21
1

Nice answer (both and all of you guys). Hopefully the OP comes back someday! – Drew Feb 15 '16 at 12:35

score 1 · Answer 2 · answered Apr 24 '15 at 06:45

Let's take a binary search as the easy example. Say you have a sorted list of 64 elements, and you're searching for a particular one. In each iteration, you halve the dataset. By the time your dataset has 1 element, you have halved it 6 times (count the arrows, not the numbers):

64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1

The reason for this is the fact that 64 = 2 ^ 6, where 2 is the base (you divide the dataset in 2 parts in each iteration), and the exponent is 6 (as you get to the bottom in 6 iterations). There is another way to write this, since exponentiation has its inverse in logarithm:

64 = 2 ^ 6
6 = log2 64

So we can see that the number of iterations scales with the base-two logarithm of the number of elements.

Complexity and binary tries

2 Answers2