The Difference Between Logarithmic Time and Linear Time
So recently I have taken it upon myself to try and learn about Big O Notation. Basically trying to figure out why certain functions run they way that they do. Also the differences between why we use this method, over another. The first two examples of time that I am learning about are Linear Time, and Logarithmic Time.
What is Linear Time?
Linear time is a representation of how long a function needs to take in order to run. The longer the size of the input the longer it will take to run. Let's say we had a function:
const findSock = (array) => {
for(const item of array){
if(item === “sock”) return “sock”
}
}
This is a representation of a linear time function. Which can be represented by O(n + 2). The number is the number of steps that we have run through in order for the function can complete itself. At the end of the day we can take that away and now this functions time complexity is 0(n). But due to the size of the input it will have to step through each item in the array and check the conditional no matter how big or small the array ends up being.
What is Logarithmic Time?
Logarithmic Time means that the running time of the logarithmic time grows in proportion to the input size and can be represented by O(log n). Essentially these times are doing the same task. But for example let's say we had a pile of laundry, and we are trying to find our socks. No matter how big or small the pile, would you look through it piece by piece? Or would you cut the pile in half and save some time? Let’s look at this function:
const findSock = (array) => {
let start = 0;
let end = array.length;
while(start ≤= end){
let mid = Math.floor((start + end) / 2);
if(array[mid] === “sock”) return “sock”
if(array[mid] < “sock”){
start = mid + 1;
}else {
end = mid -1;
}
}
}
By declaring this function we are saying that we are defining a “middle” of the array. And we are checking each item in the array with our conditional, until it is met we are essentially cutting our pile of laundry in half until we meet a true conditional. The time complexity for this function would be: O(log n) or also known as Binary Search.
At The End of The Day…
You would think that writing less code would make our runtimes faster, right? Well in this case, the Logarithmic Time Algorithm would be more efficient and faster for finding our socks. It IS more code, but it is looking through the array in halves, instead of one item at a time.
As a rule of thumb we use the Linear Time Algorithm when we want to look through an array item by item. O(n)
When we want a more efficient search tool, we would use the Logarithmic Time Algorithm instead or a Binary search. O(log n)