Technical interviews are very important when it comes to landing a job as a software engineer or developer. With the tough market we're facing, it's important to be on top of your skills in DSA. Over the next few blog posts, I will be discussing topics that have helped me learn and solve more complex DSA problems, starting off with Big 'O' Notation
What is Big "O" Notation?
This is a way to describe the time complexity of an algorithm. It is a way to describe the upper bound or worst-case scenario of how the runtime or space requirements of an algorithm grow in relation to the size of an input.
Runtime - is the measure of something in seconds, milliseconds, or any other unit
Time complexity - is how the runtime scales as the input grows. This is how we understand how a function/algorithm performs
These are the most common types of time complexity:
Constant: "O of 1"
Linear: "O of n"
Quadratic: "O of n squared"
Logarithmic: "O of log n"
Today I will go into more detail about constant and linear time complexities.
CONSTANT TIME COMPLEXITY - "O of 1"
This is the time complexity when the runtime is always the same, no matter how big the input is. For example, if you wanted to access a specific index within an array, the runtime will always be the same because it is only doing one operation. Another example of constant time complexity is the insertion and deletion of elements at the end of the array. It is usually constant-time operation because there is no need to shift or reorganize other elements.
LINEAR TIME COMPLEXITY - "O of n"
Linear time is when the runtime scales linearly as the input grows. Some examples of this includes insertion and removing elements at the beginning of an array. This requires shifting all existing elements to make space for the new element. Similarly, adding or removing elements in the middle of the array requires shifting elements.
In this function that takes in an array and adds the numbers together, it will run one step for each number in the array. If the array has 2 numbers, it will run 2 steps. If it has 100 numbers, it will run 100 steps, creating a linear scale of growth.
A course that has helped me tremendously on understanding DSA better is Brad Traversy's course! Each section has plenty of practice problems and well thought out explanations for each problem.