Jessa Daggs

Posted on

# The Big-O

### Complexity Analysis of Algorithms

Big-O notation (the letter, not the number), also referred to as the `order of the function` is a big deal when determining how to create a solution to solve a programming problem. It helps us to understand the approximate trade offs or costs of running a particular algorithm.

Big-O notation is used to classify an algorithm by the time it takes to execute that solution and how much space in memory is required in order to do so. As the algorithm grows the run time has potential to as well. Considering the time and space a solution takes will help to provide a great experience for users, teammates, and your future-self. Also, your present self because problem solving is fun!

An algorithm (the code) is the process software engineers implement or tell the computer to solve a particular problem. When determining complexity it is not the time to be optimistic. For efficient algorithms always consider the worst case scenario for the problem and code accordingly.

### Case Analysis

The case or scenario can be thought of as the interaction of the user with the algorithm from the interface. In programming the worst-case is actually the best choice. Identifying what could go wrong will decrease the opportunities to have the code fall apart. Minimize the risk. Maximize the optimization. Which means a decrease in time spent re-writing or debugging code. Understanding the best course of action for the worst case scenario goes beyond the size of the problem.

`````` // in this list we need to find a value
const arr = [1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 25, 50];

// uncomment to test
//  let case = 1; // best-case returns 0
//  let case = 7; // avg-case returns 5
//  let case = 50; // worst-case returns ll

for(let i = 0; i < arr.length; i++){
if(arr[i] === case){
return i;
}
}
``````

Because the value is found in the first iteration it is a best-case. There is no need to iterate through the entire array. Great, but what if the value isn't the first but close to the center? This would be the average-case. The iteration stops near the center of the array and returns a value increasing the number of steps required. Lastly, worst-case is when the search ends without finding the value or the value is closer to the last index.

## Time Complexity In Order Fastest to Slowest

Here we will cover some trade-offs to consider when choosing an execution method based on what needs to be accomplished.

### 1. Constant Time Complexity: O(1)

It's fast and it stays the same. This will be any algorithm where the size of the input will not have an effect on the time it takes to execute. It is `constant`. Only one step is required.

Examples: `Arrays access, Stack, Queue, and Linked List insertion and deletion`

``````//a function that returns the value at the given index of the array in a message
const constantFunFunc = array, index => `Hi, I'm \${array[index]}!`;
console.log(constantFunFunc(['Rod', 'Tina', 'Jessica', 'Jojo'], 3)); //returns "Hi, I'm Jojo!"
``````

### Logarithmic Time Complexity: O(log n)

Reduces the size of the input at a decreasing rate. The runtime of a logarithmic algorithm initially increases but only grows in relation to how many choices are left after narrowing down the values to look through. It can be thought of as the opposite of the Quadratic time complexity.

Examples: `Binary Search Tree`

``````// array to be searched by the value
const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 25, 50];
const bSearch = (collection, target) => {
// set a start to the zeroth index
let start = 0;
// set end to the last index the array
let end = collection.length -1;
// iterate through the indices
while(start <= end){
// set the middle index
let middle = Math.floor((start + end) / 2);
// if value at the middle index is target return true
if(collection[middle] === target){
return true;
// if the value is less than the target re-assign start the the middle +1
} else if(collection[middle] < target){
start = middle + 1;
} else {
// value is greater than the target re-assign end the middle -1
end = middle - 1;
}
}
// if the value is not in the given collection return false
return false;
}

console.log(bSearch(array, 25)); //returns true
``````

### Linear Time Complexity: O(n)

An algorithm whose growth is directly affected by the size of the input data. The iteration stopping early in the execution would be considered a best-case scenario. The execution time would reduce in that situation but there is potentially the need to be able to access any and all information contained within our data.

Examples: `Array iteration`

``````// create a function that takes an array
const iterator = (arr, target)=>{
//loop through the array and push the value into a new array if it is equal to the target
let yourArray = [];
for(let i = 0; i < arr.length; i++){
if(arr[i] === target){
yourArray.push(arr[i]);
}
}
// return the new array
return yourArray;
}
const myArray = ['504424.14', '223141.21'];
console.log(iterator(myArray, '504424.14')) //return ['504424.14']
``````

As the number of elements grows the execution time grows as well. The execution of one algorithm that is lower on the Big-O scale within another one has the potential to be considered quadratic.

Examples: `Bubble Sort, Nested for loops`

``````
const eats = [['hummus', 'smoothie'], ['crawfish', 'snowball'], ['fries', 'pizza'], ['Neyow's','gumbo']];
//find the first letter in the array of nested arrays

//iterated through the array
for(let i = 0; i < eats.length; i++){
//iterate through the array at the index of the outer array
for(let j = 0; j < eats[i].length; j++){
// log the first letter in each
console.log([`\${eats[i][j][0]} or \${eats[i][j][1]}`]);
}
} // returns ['h or s']; ['c or s']; ['f or p']; ['N or g']
``````

## Conclusion

Some other time complexities are: Exponential Time O(2^n) when the rate of growth doubles as the input increases. Factorial Time O(n!) when the rate of growth is determined by the number of integers from 0 to n. If you would like a brain teaser see Bogosort.

Thank you for reading. I appreciate your time. Happy Coding and remember efficiency is key!