Divide and Conquer: A Big O Pattern

As stated in my last post, I have been discussing Big O and how we can refactor our code to make it the most efficient it can be. To take a look at that post, click here.

Anyways, one common pattern we can use when trying to solve a Big O problem is to Divide and Conquer (DnC). What is DnC? When you divide and conquer, you are dividing a data set into smaller chunks, and then repeating a process with a subset of data. This type of pattern can greatly decrease the time complexity.

Imagine if you we given the following challenge:

Given a sorted array of integers, write a function called “search” that accepts a value and returns the index where the value passed to the function is located. If the value is not found, return -1

One way to solve this issue is by writing the following code:

This isn’t horrible, but the time complexity is O(n). However we are able to make that much quicker by doing the following:

Rather than the original linear search we can complete the task with a binary search. With this code, we are checking the middle of the array to see if it is greater or less than the given value. Then, if it isn’t equal, it moves to either the left or right depending on whether it is greater or less than. With this code, the time complexity is Log(n) and much quicker than the original.

Linear search goes through the entire array to try and find the answer. However, because we are working with a sorted array, we can divide it in half to try and find our answer. Once we divide the array, we then see if the value we are searching for is greater than or less than the middle.

This is just one example to how we can make our code quicker!

--

--

--

Software Engineer

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

Recommended from Medium

Solve These Three Simple Problems Before Your Next Interview

Bitonic (Merge) Sort | Explanation and Code Tutorial

Memory Cost Model in Qubole Presto

Singleton Design Pattern

How I Tackle my Projects @ Alx — Holberton Way

TypeORM MongoDB Review

How demo-oriented programming makes you better

Plotting scatter ,line & bar combo using Py script Power BI in 2 minutes

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
Thomas Muscarello

Thomas Muscarello

Software Engineer

More from Medium

Improve the Code Quality in Python Projects using Pre-Commit Hooks

Let's talk about a couple of Special types

Taking Time to Appreciate Netflix: Reflections on my First JavaScript Project

Tests Tests and More Tests: JavaScript Unit Testing with Jest