O(log n): Logarithmic Time

Logarithmic time is one of the most powerful complexity classes in computing. An O(log n) algorithm does not look at every element. Instead, it eliminates half of the remaining possibilities at each step. This halving strategy means that even enormous inputs require surprisingly few operations. Searching a sorted list of one billion elements takes at most 30 comparisons, because you only need to halve a billion 30 times to reach a single element. Why it matters: a sorted index lets the database cut the search space in half at every step. Doubling your table size adds only one extra comparison, which is why indexed queries barely slow down as data grows. The Power of Halving The logarithm answers a simple question: "How many times must I divide n by 2 to reach 1?" Start with 1,000 elements

About This Interactive Section

This section is part of the Complexity: Intermediate lesson on DataDriven, a free data engineering interview prep platform. Each section includes explanations, worked examples, and hands-on code challenges that execute in real time. SQL queries run against a live PostgreSQL database. Python runs in a sandboxed Docker container. Data modeling problems validate against interactive schema canvases. All content is framed around what data engineering interviewers actually test at companies like Meta, Google, Amazon, Netflix, Stripe, and Databricks.

How DataDriven Lessons Work

DataDriven combines four interview rounds (SQL, Python, Data Modeling, Pipeline Architecture) with adaptive difficulty and spaced repetition. Easy problems get harder as you improve. Weak concepts resurface until you master them. Your readiness score tracks progress across every topic interviewers test. Every lesson section ends with problems you solve by writing and running real code, not by picking multiple-choice answers.