Python Projects for Beginners a ten-Week Bootcamp Approach to Python Programming

Table 9-1. Big O Notation growth rate comparison⁶

Number of Elements	Simple Search	Binary Search
The runtime in Big O Notation	O(n)	O(log n)
10	10 ms	3 ms
100	100 ms	7 ms
10,000	10 sec	14 ms
1,000,000,000	11 days	32 ms

We can clearly see that efficient algorithms can help to improve our programs speed. Therefore, it’s important to keep efficiency and time complexity in mind when writing your code. The picture in Figure 9-2 depicts the complexity of the number of operations over the number of elements.

Figure 9-2. Big O Notation complexity over time chart
Not all of Big O Notation is covered here, so be sure to do some further research if you’d like to understand these concepts further. This is simply an introduction into what Big O is and why it is important when writing our programs.

Hash Tables

When we originally covered dictionaries, we went over hashing very briefly. Now that we’ve covered Big O Notation, understanding hash tables and why they’re important is much easier. Dictionaries can be accessed in O(1) complexity because of how they are stored in memory. They use hash tables to store the key-value pairs. Before we cover hash tables though, let’s have a quick refresher on the hash function and how to use it:
>>> a, c = 'bo', "bob"
>>> b = a
>>> print(hash(a), hash(b), hash(c))
ChAptEr 9 AdvAnCEd topiCs ii: ComplExity
From the preceding code, we would get the same values for a and b and a separate value for the hash of c. Hash functions are used to create an integer representation of a given value. In this case the integer for the string “bo” and the variables a and b are the same; however, “bob” and the c variable are completely different because they have a different value.
When dictionaries store key-value pairs into memory, they use this concept. A hash table is used to store a hash, a key, and a value. The hash stored is used for when you need to retrieve a given value by the key. Take Table 9-2, for instance. There are three key-value pairs in place, all with different hash values. When you want to acces the value for name, you would write:
>>> person[ "name" ]
What happens is Python hashes the string “name” and looks for the hash value rather than the key itself. You can think of this like retrieving an item within a list by its index. This is much more efficient as you can retrieve values based on hashes almost instantly at O(1) time.
Table 9-2. Logical representation of
Python hash table