As you can see from the illustration above, the memoization method gets rid of the redundant part of the problem and we just have to calculate and store the left part of our call tree. Hope you guys like the illustration I drew! Since we just have to calculate the leftmost branch of the tree to compute the sequence, our complexity becomes only O(n)! Much better eh?

## Saturday, 22 March 2014

### Complexity and O(n) Notation

As you can see from the illustration above, the memoization method gets rid of the redundant part of the problem and we just have to calculate and store the left part of our call tree. Hope you guys like the illustration I drew! Since we just have to calculate the leftmost branch of the tree to compute the sequence, our complexity becomes only O(n)! Much better eh?

## Monday, 17 March 2014

### Binary Search Trees

This week we analyzed a specific version of binary trees called the binary search trees. They are quite similar with the addition of a simple rule. Every left child of the root node must have a smaller value than root's value and every right child has a bigger value than root's value. So a simple binary search tree would look like this.

This special version of binary tree has some fascinating properties. For example, to find the smallest or the highest value, you just have to go to leftmost or the rightmost node without even comparing any value! It is also terrific at finding a given value in the tree, hence its name. To find a value, you just compare it to a node starting from the root and then recursively search through left subtree if given value is smaller than node or scour the right subtree if the value is greater!

This special version of binary tree has some fascinating properties. For example, to find the smallest or the highest value, you just have to go to leftmost or the rightmost node without even comparing any value! It is also terrific at finding a given value in the tree, hence its name. To find a value, you just compare it to a node starting from the root and then recursively search through left subtree if given value is smaller than node or scour the right subtree if the value is greater!

Subscribe to:
Posts (Atom)