Published
Edited
Jan 2, 2020
1 star
// This function multiples the input by itself
constantTime = (n) => {
return new Promise((resolve, reject) => {
startTest('constantTimeStart')
// Constant time because it will always run 1 operation, regardless of the input size
const operation = n * n
resolve(endTest('constantTimeStart', 'constantTimeEnd'))
})
}
constantTime(100).then(res => `This algorithm ran in ${res} milliseconds.`)
// This is a binary search algorithm
logarithmicTime = (n) => {
return new Promise((resolve, reject) => {
startTest('logarithmicTimeStart')
// Prep data set
const dataSet = buildArray(n)
const startingIndex = dataSet[0]
const endingIndex = dataSet[dataSet.length - 1]
// By making the searchTarget the farthest possible from the middle, we ensure worst-case performance
const searchTarget = dataSet[0]
// Run recursive binary search
const runBinarySearch = (dataSet, target, start, end) => {
console.log('Running search:', dataSet, target, start, end)
// If our dataSet is only 2 long, just check which one is the target and return
if (dataSet.length === 2) {
console.log('Search target found:', dataSet[end] === target ? dataSet[end] : dataSet[start])
resolve(endTest('logarithmicTimeStart', 'logarithmicTimeEnd'))
}
// Find the middle point
const middle = Math.floor((dataSet[start] + dataSet[end]) / 2)
// If the target is the middle, we're done
if (target === dataSet[middle]) {
console.log('Search target found:', dataSet[middle])
resolve(endTest('logarithmicTimeStart', 'logarithmicTimeEnd'))
}
// If target is greater than middle, start search over with new parameters
if (target > dataSet[middle]) {
return runBinarySearch(dataSet, target, dataSet[middle], end)
}
// If target is less than middle, start search over with new parameters
if (target < dataSet[middle]) {
return runBinarySearch(dataSet, target, start, dataSet[middle])
}
}
return runBinarySearch(dataSet, searchTarget, startingIndex, endingIndex)
})
}
logarithmicTime(10000).then(res => `This algorithm ran in ${res} milliseconds.`)
linearTime = (n) => {
return new Promise((resolve, reject) => {
startTest('linearTimeStart')
let i = 0
while (i <= n) {
// We're not really performing any operations, just incrementing and iterating
console.log(i)
if (i === n) {
resolve(endTest('linearTimeStart', 'linearTimeEnd'))
}
i++
}
})
}
linearTime(10000).then(res => `This algorithm ran in ${res} milliseconds.`)
quadraticTime = (n) => {
return new Promise((resolve, reject) => {
startTest('quadraticTimeStart')
const dataSet = buildArray(n)
// Loop through each item in the data set
dataSet.forEach((i) => {
// Loop through the data set *again* for each item in our data set
dataSet.forEach((j) => {
// I'm not logging the integers because the console gets finicky with large data sets, but without any // logging at all, the browser seems to make optimizations and the reporting is faulty.
if (i === j) console.log(i)
})
})
resolve(endTest('quadraticTimeStart', 'quadraticTimeEnd'))
})
}
// IMPORTANT: Be careful. Numbers above 10,000 are going to get insane and break your browser.
quadraticTime(10000).then(res => `This algorithm ran in ${res} milliseconds.`)
polynomialTime = (n) => {
return new Promise((resolve, reject) => {
startTest('polynomialTimeStart')
const dataSet = buildArray(n)
// Loop through each item in the data set
dataSet.forEach((i) => {
// Loop through the data set *again* for each item in our data set
dataSet.forEach((j) => {
// Loop again!
dataSet.forEach((k) => {
if (j === k) console.log(k)
})
})
})
resolve(endTest('polynomialTimeStart', 'polynomialTimeEnd'))
})
}
// IMPORTANT: Be careful. Numbers above 1,000 are going to get insane and break your browser.
polynomialTime(100).then(res => `This algorithm ran in ${res} milliseconds.`)
runTestSuite()
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
