>> "Let’s say we have 1000 records in our film table. To find “Academy Dinosaur” our database will need to do 1000 operations (comparing the title in each row).

>> "Let’s say we have 1000 records in our film table. To find “Academy Dinosaur” our database will need to do 1000 operations (comparing the title in each row)." > No you don't. If your table is sorted, [...] on average, to find any title, you will need n / 2 operations (so not 1000, but 500, in this example - this part is plain wrong as it's written). Of course, n / 2 is linear in n, so the complexity stays the same. If something is sorted, search happens in O(log N) which is not linear: start with compare at N'=N/2. If "less than", go to N''=N'/2; if "greater than" go to N''=3N'/2. Etc. If the data is not sorted, then yes, you will need N lookup operations.