Run Time Complexity for Beginners (like me!)

A majority of the time when we're writing javascript and algorithms, we know that as in all of programming, there is almost always a better way to write something. Sometimes it looks nicer, or may just seem easier to understand, but Run Time Complexity specifically references the amount of time that it takes to run the code you've written or in simpler terms, it describes the performance of an algorithm.

So how do we figure out how we can find out what the complexity of our algorithms could be. There are different kinds of 'runtime', which is decided based on how your algorithm runs. For example, if we have a function that requires a for loop of any kind, and given a single argument, the for loop has more items to iterate through, based on the length of input. For instance, reversing a string.

function rev(str){
    let rev = ""
    for(let i = str.length - 1; i >= 0; i--){
        rev += str[i]
    }
    return str
}

For every input, our computation has to iterate through the string one more time for every additional character in the string. Fairly simple, and because the we're doing one more step for one more character, that would be referred to as a linear runtime. There's a direct correlation between the number of characters and the amount of steps at a 1:1 ratio, thus, linear.

Now, if we were to have something that has more than one for loop, and occasionally, it's necessary. If there are two for loops for whatever function, there is now double the amount of processing power needed. Let's say we have a function that needs to iterate once, and then iterate again. Let's take an instance where a function has nested for loops. This indicates that for every additional input character given, the function now has to do way more work. An example shown to me was a function to console.log a staircase.

function stairs(input){
    for(let row = 0; row < input; row++){
        let stair = '';

        for(let column = 0; column < n; column ++){
            if(column <= row){
                stair += '#';
            }else {
                stair += ' ';
            }
        }
        console.log(stair)
    }
}

Here, as the input increases, the steps the function needs to perform increases exponentially. With an input of 2, we had to perform 4 actions. With 3, we had to perform 9 things and so on. This is what's referred to as Quadtratic runtime, or n*n things (N^2).

The most Common that I've read about are as follows:
Linear Time (discussed above)
Quadratic Time (discussed above)
Constant Time
Exponential Time
Logarithmic Time
Quailinear Time

Lets briefly touch on each of the remainders.

For Constant Time, the word constant is key. All this means is that regardless of input, the operation will always take the same amount of time. so something like this:

function FifthItem(list){
    return list[4]
}

regardless of size, this will always computate at the same runtime, thus the name, constant. (O(1))

Exponential time is considered, among those listed, to be the least efficient. The reason being is that an exponential timed solution means that adding only one additional character, doubles the processing power needed for the solution. This is obviously very bad. (2 ^ n)

Logarithmic Time is if the elements given are doubled, but the outcome does NOT double the amount of work needed. Usually searching through a sorted array of data, or any kind of search, these are usually running with logorithmic time. (log(n))

Lastly, Quasilinear Time. Similair to Logarithmic Time, this is when doubling the number of elements being iterated does not double the amount of work, but adds to it by 1 plus a little more. This is one I dont fully understand yet, but that's why I'm here. (n * log(n))

That's all for today!