As always, the best way to learn such concepts in Computer Science is to start with a relatable example. So, we'll pick Soma Stories. We have two groups of users, writers and readers. When you register, we store your username and password, so that next time you come to the platform, enter your username and password, we can search our list of users and grant you access without you having to register again.
Let's start with a snapshot of our user's database:
# User database for Soma Stories
users_db = [
{"username": "m_ochieng", "pw": "Luo_Pride_254"},
{"username": "shi_wambui", "pw": "Nyumbani_M0re"},
{"username": "kamau_j", "pw": "Kijabe_Hills_9"},
{"username": "atieno_l", "pw": "Kisumu_Sunset!"},
{"username": "b_wafula", "pw": "Rainy_Day_BGM"},
{"username": "p_mutua", "pw": "Machakos_Best"},
{"username": "sarah_j", "pw": "Coast_Vibe_001"},
{"username": "d_njoroge", "pw": "Coffee_Farm_22"},
{"username": "kip_rotich", "pw": "Eldoret_Champ"},
{"username": "h_mohamed", "pw": "Mandera_Safe"},
{"username": "jane_njeri", "pw": "Hustle_Sasa_99"},
{"username": "otieno_j", "pw": "Lakeside_Magic"},
{"username": "muthoni_p", "pw": "Tea_Zone_2026"},
{"username": "k_kariuki", "pw": "MtKenya_High"},
{"username": "ali_hassan", "pw": "OldTown_Msa"},
{"username": "chebet_r", "pw": "Kericho_Green"},
{"username": "w_wekesa", "pw": "Webuye_Falls"},
{"username": "nyambura_g", "pw": "Ruiru_Living"},
{"username": "m_mwangi", "pw": "Nairobi_Techie"},
{"username": "faith_w", "pw": "Jambo_Kenya_254"}
]There are several things that can happen to this data:
- A User might login
- Data Scientist might want to sort the list, alphabetically
- A cyber security analyst might want to check which password is weak
- We might want to check if a username is already taken
All these actions involve searching and sorting. The steps we take when searching or sorting are what we call Algorithms.
In this session, we're only going to talk about Sorting and Searching.
Before we jump into the actual algorithms, there are five important things to understand:
- for loops and while (this will make you cry!)
- if statements
- lists
- Item index
- Big O (not as big as it sounds).
The first four concepts were discussed in detail during the live class. We will talk more about the 5th one, The Big O notation. Before we dive deeper, let's first take a step back. From our previous classes, we discussed that the whole business of computing is data. Storing, manipulating and presenting data. Throughout these stages, we need to answer one question, how much time it takes for the data to go from one stage to another. The Big O notation is represented as this, O(n*) the * represents other parameters we can use, such us O(n^2)
Big O
O(1) – Constant Time (The Gold Standard)
Imagine you are standing at the entrance of a Matatu stage (bus station). You have one simple question: "Is there at least one Matatu here?"
Scenario A: There is 1 Matatu. You look at the first slot, see a vehicle, and say "Yes, it's busy." (1 look)
Scenario B:There are 1,000 Matatus. You look at the very first slot, see a vehicle, and say "Yes, it's busy." (1 look)
Whether there are a million matatus or 1, it only takes you a second to look. Hence we can say, whatever the data you put into the system in this case, the time it takes to process that data will be constant.
O(n) – Linear Time (The Fair Walk)
You have to walk down the line and check every single Matatu one by one until you find your friend. If there are 10 Matatus, it takes 10 checks. If...