So what the is O(log n) Time Complexity Anyway?

What is Time Complexity?

What is a logarithm?

A quantity representing the power to which a fixed number (the base) must be raised to produce a given number.

2^x = n
log_2 n
x = log_2 n
(2^x = n) = (x = log_2 n)

What about in Code?

def binary_search(list1, low, high, n):   if low <= high:   mid = (low + high) // 2   if list1[mid] == n:      return mid   elif list1[mid] > n:      return binary_search(list1, low, mid — 1, n)   else:      return binary_search(list1, mid + 1, high, n)   else:      return -1
[1, 3, 5, 8, 12, 13, 15, 16, 18, 20, 22, 30, 40, 50, 55, 67]
[1, 3, 5, 8, 12, 13, 15, 16, 18, 20, 22, 30, 40, 50, 55, 67]
[1, 3, 5, 8, 12, 13, 15, 16, 18, 20, 22, 30, 40, 50, 55, 67]
[1, 3, 5, 8, 12, 13, 15, 16, 18, 20, 22, 30, 40, 50, 55, 67]
16 * (1/2)^4 = 1
n * (1/2)^4 = 1
n * (1/2)^x = 1
n * 1/2^x = 1
n/2^x = 1
2^x * n/2^x = 2^x
n = 2^x

A quantity representing the power to which a fixed number (the base) must be raised to produce a given number.

(n = 2^x or 2^x = n) = (x = log_2 n)

Is There an Easier Way to Tell?

Conclusion

--

--

--

Software Developer working my way through the world and sharing what I learn with all of you. Personal Site — www.aidantilgner.dev

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Databricks Pyspark & Spark SQL — Get File Names when reading data from ADLS into Azure Databricks

Get Started with Splunk: Part — I: Search the Data Using Splunk

The Future Of Test Data

Section 3 — Social networking and human relationships

BLOG “AS MY PORTUGUESE GRANDFATHER USED TO SAY”. Reinvent yourself in human relationships. REINVENT YOURSELF IN THE COVID-19 ERA. By José Antonio Ribeiro Neto (Zezinho). #reinventyourself #selfimprovement #socialnetwork #socialmedia #graph #networking #sixdegreesofseparation #graphtheory #relantionships #dunbartheory

SQL Gotcha: When an OUTER JOIN Accidentally Becomes an INNER JOIN

SpringBoot Interview questions.

The Art of Writing Technical Documentation

Platform Engineering — The Invisible Iron Man Suit That Helps Your Company Fly

Microservices Architecture

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Aidan Tilgner

Aidan Tilgner

Software Developer working my way through the world and sharing what I learn with all of you. Personal Site — www.aidantilgner.dev

More from Medium

Why coding still matters

Self-Discipline Is The #1 Obstacle For Self-Taught Engineers

A person coding.

The “Insane Tech Hiring Mark”

Render That Fender!