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

Discover Iron Rates In Euros From LME

Setting up SSH for Git (Windows)

CS373 Spring 2022: Abhinav Mugunda

Why 2019 is the year for PLM software

How to build REST API client using Feign in Spring Boot

Release Apps Faster with Fastlane

Arduino Meets Pixy

Introduction to Agile and Lean Practices for Data-Driven Product Development

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

Is pair programming a match for you?

The Kids Are Alright

A screenful of code.

Debugging: the map is not the territory