It's Been a While

Well, it's been only like, 2 months since I last wrote in this. My apologies.

I want to talk about O(log n) and O(nlog n) search algorithms. Mostly about how they confused me when I first learned about them. Now I sort of get them.

The best example of a sorting algorithm with O(log n) is a search function for a binary tree. We have the root and the nodes and leaves beneath it. To the left of the root is all values lower than the node. To the right, we have all values greater than the node. All subsequent nodes follow this pattern, so we have a tree with all its values ordered.

Now, suppose we have a binary tree with 16 leaves, each leaf sharing a node with another leaf. That means above it there are 8 nodes. If this pattern repeats itself all the way to the top, that means there are 4 nodes, then 2, and finally 1. As a mathematical function, the binary tree grows at a rate of 2^n. So if we wanted to find a value all the way at the bottom of a tree with 16 leaves, we would have to go through 4 nodes above it, because 16 = 2^4, and a tree starts with 2^0 nodes. In order to find the value, we traverse the tree by checking nodes. If the node is not the desired value, we check to see if the node is greater or less than the value. Using this knowledge, we can eliminate half of the values in the tree, because all values greater than the node lie on the right, and all values less than the node lie to the left. This process repeats itself until we finally reach the leaves of the tree, or the value is found. This gives us a worst case of O(log n), with base 2. Our best case scenario would be O(1) if the root was the desired value. A binary tree is a great way to store values because of its O(log n) properties. Except in cases with small values, a binary tree will sort faster than a linear search, and its runtime increases slowly as the tree grows.

Here's a good link explaining it

O(nlog n) would occur if the tree was unsorted, and we needed to go through the entire thing and sort it. I'm actually still not sure how this works out, but I heard recursion is magic and  I can believe that. I'll write a new blog post when I finally understand it. So, I'll see you guys again in like, a year or something.

Well, this is my first blog post ever! Never would have thought I'd write a blog since I think I'd come off as too crazy or too pretentious ("Internet, I'm right and you are wrong! Read my blog!"), but apparently it's a requirement to pass my class.

So, Object Oriented Programming. I'm going to pretend I understand that properly and write a few things down about it. Maybe just spew a few buzzwords out.

OOP is a way of putting code together in a package to that functions and variables can all be together in the same place. I think of an object as a container for a variety of functions and variables. Apparently, every variable is an object in Python, such as ints, floats, strings, and lists. As long as it has values and functions attached to it, it's an object. Every source I read remarks about how confusing it can be. They understate the pain it causes.

Anyways, here's my first blog post. I don't know if I'll actively write in here outside of class requirements, but it's early days. Thanks for reading!




- Magical Unicorn