Be an Effective and Efficient Programmer
What does it mean to write efficient code?
Efficient: achieving maximum productivity with minimum wasted effort or expense.
Welcome to my humble blog. So glad you are here! Join me in a little investigation of the basics of Big O Notation and Code Efficiency.
What is Code Efficiency…
Its a buzzy term that gets thrown around in meetups, lectures, and blogs. Broadly used to describe the speed and reliability of code, it is closely linked with algorithmic efficiency and the speed of runtime execution for software. In a time where AI, scalability, and Machine Learning are at the forefront of Software Development, the topic comes up time and time again.
What is Big O Notation…
It’s a tool used in Computer Science to describe the performance and efficiency of an algorithm and analyze overall performance. It is used to determine the worst-case scenario for time required, or space used to complete execution of an algorithm. Big O is a valuable tool to determine the best implementation of a function based on performance, and provides us with a way to talk formally about how the runtime of an algorithm changes based on input.
Time Complexity vs Space Complexity
Big O notation is used to measure time complexity and space complexity. Time Complexity: the amount of small operations that must be performed to complete operation.
Space Complexity: the amount of additional memory that must be allocated to run the code in an algorithm. Often referred to as Auxiliary Space Complexity, meaning it refers to the space being taken up by the algorithm, not including space being taken up by the inputs
Types of Complexity
Time Complexity can fall within several different types. Here are a few of the more common types.
1. Constant / O(1): will always execute in the same time or space, regardless of size of the input data set.
2. Logarithmic / O(log n): the power to which a fixed number must be raised to produce a given number
3. Linear / O(n): complexity will grow in direct correlation to the size of the input data
4. Linearithmic / O(nlog n): performs an O(log n) operation on each item in the input.
5. Quadratic / O(n²): performance is directly proportionate to the squared size of the input data
Some Helpful General Rules when Determining Time and Space Complexity …
Disclaimer: these are general rules that can prove to be a helpful starting point, but they will not always work.
Time Complexity
- Arithmetic operations are constant
- Variable assignment is constant
- Accessing elements in an array (by index), or an object (by key) is constant
- In a loop the complexity is the length of the loop times the complexity of whatever happens inside that loop
Space Complexity
- Most primitives are constant space. (booleans, numbers, undefined, null)
- Strings require O(n) space, where n is the length of the string
- Reference types are generally O(n), where n is the length of the array or number of keys for objects.
Lets Evaluate Some Examples!
In the above example the number of operations grows roughly proportionate with n. So if n is 100, then i will be added to the total 100 times.
Time complexity for addUpToN will be linear / O(n)
As far as space complexity, addUpToN has 2 variable assignments(total and i). These variables get reassigned as the loop completes its operation, but the space taken up by these variables remains the same no matter what the input data set size will be.
Space Complexity will be constant / O(1)
Here we have 3 simple operations(multiplication, addition, division). Regardless of the size of n the number of operations remains the same.
Time Complexity of addUpToNAgain is constant / O(1)
There is only one value that will be returned. The input value does not change the space being allocated to this function. therefore space complexity is also linear / O(1)
Here we have a linear O(n) operation nested within another O(n) operation. As the input n scales, the runtime squares.
Time Complexity of sumEachPair is quadratic / O(n²)
If we recall from the helpful general rules earlier, reference types are generally O(n), which in this case is true. The amount of space that must be allocated directly correlates to the input value.
Space Complexity is linear / O(n).
Recap…
Understanding the time and space complexity of the code we write is an important tool we can utilize to ensure we maintain the fastest runtimes and fastest execution possible, all while staying within the bounds of the physical memory of the system it is intended to run on.
1. To analyze the performance of an algorithm, we use Big O Notation
2. Big O Notation can give us a high level understanding of the time and space requirements of an algorithm
