Big O Time

Here's a great way to approximate the Big O time of your algorithm: just run it with differently sized inputs.

That's right, that's all you have to do* (*there's more to it, we'll get to it in a sec).  You don't need to follow your inputs around, count any loops, look for best case and worse case scenarios.  You can get a pretty good approximation by following the steps below.

1. Speed test your algorithm.  Make sure you have at least 3 inputs - if you're working with an array, make sure there's 3 elements, if you have a string make sure there's at least 3 letters, etc.  Larger inputs will make this test more accurate.  Note down how fast your algorithm was.

2. Double the number of inputs.

3. Speed test your algorithm again.  Got a number? Good.

4.  Now, divide the second speed test result by the first one.

Once you've got that ratio, you're good to go!  Simply compare your ratio to the following chart:

RatioBig O time
approximately 1O(1)
approximately 2O(n)
approximately 4O(n^2)
approximately 8O(n^3)

That's it!  This doesn't cover all cases, but it does cover a huge amount of them.

Here's some code to test it out:


let input1 = [1,2,3,4,5]
let input2 = [1,2,3,4,5,6,7,8,9,10]

function speedDemon0(arr) {
let sum = 0

return sum
}

function speedDemon1(arr) {
let sum = 0

for (let i=0;i<arr.length-1;i++) {
sum += arr[i]
}

return sum
}

function speedDemon2(arr) {
let sum = 0

for (let i=0;i<arr.length-1;i++) {
for (let j=0;j<arr.length-1;j++) {
sum += arr[i] + arr[j]
}
}

return sum
}

function speedDemon3(arr) {
let sum = 0

for (let i=0;i<arr.length-1;i++) {
for (let j=0;j<arr.length-1;j++) {
for(let k=0;k<arr.length-1;k++) {
sum += arr[i] + arr[j] + arr[k]
}
}
}

return sum
}

console.log("=====")
start = Date.now()
for (u=0;u<10000000;u++) {
speedDemon0(input1)
}
end = Date.now()
timeElapsed1 = end - start
console.log(`input1 time: ${timeElapsed1} ms`)

console.log("=====")
start = Date.now()
for (u=0;u<10000000;u++) {
speedDemon0(input2)
}
end = Date.now()
timeElapsed2 = end - start
console.log(`input2 time: ${timeElapsed2} ms`)
console.log('+++++')
console.log(`speedDemon0 input2 to input1 ratio: ${timeElapsed2/timeElapsed1}`)

console.log("=====")
start = Date.now()
for (u=0;u<10000000;u++) {
speedDemon1(input1)
}
end = Date.now()
timeElapsed1 = end - start
console.log(`input1 time: ${timeElapsed1} ms`)

console.log("=====")
start = Date.now()
for (u=0;u<10000000;u++) {
speedDemon1(input2)
}
end = Date.now()
timeElapsed2 = end - start
console.log(`input2 time: ${timeElapsed2} ms`)
console.log('+++++')
console.log(`speedDemon1 input2 to input1 ratio: ${timeElapsed2/timeElapsed1}`)

console.log("=====")
start = Date.now()
for (u=0;u<10000000;u++) {
speedDemon2(input1)
}
end = Date.now()
timeElapsed1 = end - start
console.log(`input1 time: ${timeElapsed1} ms`)

console.log("=====")
start = Date.now()
for (u=0;u<10000000;u++) {
speedDemon2(input2)
}
end = Date.now()
timeElapsed2 = end - start
console.log(`input2 time: ${timeElapsed2} ms`)
console.log('+++++')
console.log(`speedDemon2 input2 to input1 ratio: ${timeElapsed2/timeElapsed1}`)

console.log("=====")
start = Date.now()
for (u=0;u<10000000;u++) {
speedDemon3(input1)
}
end = Date.now()
timeElapsed1 = end - start
console.log(`input1 time: ${timeElapsed1} ms`)

console.log("=====")
start = Date.now()
for (u=0;u<10000000;u++) {
speedDemon3(input2)
}
end = Date.now()
timeElapsed2 = end - start
console.log(`input2 time: ${timeElapsed2} ms`)
console.log('+++++')
console.log(`speedDemon3 input2 to input1 ratio: ${timeElapsed2/timeElapsed1}`)

And here's my results:

Why does this work?  It's related to what Big O actually means in practical terms.  Doubling our inputs means doubling our n, whatever that n is.  So, if we are operating in O(n^2) time, that means that if we double our input, we substitute 2n for n, which raises our execution time from n^2 to (2n)^2, which is 4n^2, which is 4 times larger than n^2 - you may note that (4n^2)/(n^2) = 4, which is the same division we did in step 4.  Likewise, if we're operating in O(n^3) time, that means that doubling our input raises our execution time from n^3 to (2n)^3, which is 8n^3, which you can see is 8 times bigger.

So, what do we do about more exotic scenarios, like where our Big O time is, say, n log n?  We can use the same principle of substitution to test a prediction about our Big O time.  What is (2n log 2n)/(n log n)?  Well...that depends on what n is.  To do a proper test here, you'll need to actually substitute in how many inputs you have.  If we have 5 inputs like in our code example and then we doubled to 10, the above expression calculates to 2.86.  So somewhere around a little less than 3 would be a good ratio to look for.

Likewise, if we were looking for exponential time, we would calculate 10! and divide by 5!, which gives us...30,240.  Doubling our inputs would increase our time to run by over 30,000 times.  Exponential time is really, really slow!

Comments

Post a Comment

Popular posts from this blog

The Sorting Hat

Image
Here's a lesson about the difference between theory and practical applications. Everyone knows about  bubble Sort  and  merge Sort  - they're probably the first two sorting algorithms you learned.  Everyone also knows that (1) bubble sort sucks and (2) this is due to the fact that its average time complexity is O(n^2), aka the worst time complexity.  It even generally performs worse than things like insertion sort and  selection sort , the "a D- is still a passing grade" of sorting algorithms. While all these things are true, there's a more important truth: always test your code. While reading  The Imposter's Handbook by Rob Conery  the other day and flipping through the comparison sort algorithms he provides, I decided, Why not actually test out this code?   And, the  speed test demon  that I am, my test involved sorting out his [23,4,42,15,16,8] array one million times with bubble sort and with merge sort, and I got this res...
Read more

Kadane's Algorithm

Imagine it is 1977.  You do not have a degree in computer science.  You have not spent months grinding leetcode.  You are given a algorithm problem that a decorated mathematician has already created what looks like an optimal solution. And then in less than a minute you come up with a better answer. You are  Jay Kadane , and the problem that you have solved is the maximum subarray problem. The maximum subarray problem gives you an array of numbers and asks you to pick out the subarray with the largest sum.  The problem is trivial if all the numbers are positive: [ 1 , 5 , 1 , 3 , 2 ] <- the largest subarray is obviously the entire array But what if you've got some negative numbers thrown in there? [ 1 , 5 , -1, 3 , - 2 ] <- sure, you don't want the negatives. But isn't taking the -1 worth the +3? A brute-force solution materializes pretty easily: just create every subarray and find the biggest sum: [ 1 ] = 1 [ 1 , 5 ] = 6 [ 1 , 5 , - 1 ] = 5 ...
Read more

Loose Equality, the Null Operator, and Other Oddities

 Here's a fun bit of code to run: console . log ( '0.5' == 0.5 ) //evaluates to true console . log ( '0.5' === 0.5 ) //evaluates to false The first equality statement is what's known in JavaScript as "abstract equality comparison", which people usually refer to as "loose equality."  Loose equality compares objects only after doing a type conversion - so even though '0.5' is a string and 0.5 is a number, JavaScript sort of jams them together and says "sure, good enough."  It's weird, but convenient sometimes when dealing with data that's really (in an abstract sense) numbers but could come through the pipes as either a number or a string. People have written surprisingly long algorithms to precisely define what  abstract equality  and  strict equality (aka, normal equality)  mean in JavaScript and other languages that adhere to the ECMAScript standards.  But for our regular usage, things that are to people the same ...
Read more