What is an Algorithm?
These are a set of instructions for completing a task. Can also be defined as a set of steps a program takes to complete a task.
It is important for developers to know when and why they should use a certain algorithm by understanding the problem and breaking it down into steps. This is called Algorithmic Thinking.
An algorithm must contain a specific set of instructions in a particular order:
- Start from the beginning.
- Compare the current value to the target value.
- Move sequentially.
- Reach the end of the list.
- Each step in an algorithm needs to be explicitly clear and not have substeps.
An algorithm should have correctness and efficiency
Correctness is when an algorithm takes in an input and gives an output without taking an infinite amount of time.
Efficiency. This can be broken down into two;
- Time Complexity: This is the amount of time taken to complete a task
- Space complexity: This is the amount of memory taken by the computer
What exactly is Time Complexity?
I’ll explain using the Big O notation.
What is the Big O?
Big O notation is a mathematical notation used to describe the time complexity of algorithms. In other words, It calculates the time taken to run an algorithm as the input grows.
Reading the runtime of a Linea Search is O(n), which can be read as Constant Time. This means that no matter where we are on the search we take the same amount of time to compare a number to the target number
The runtime of Binary Search is written as O(log n). This is known as the logarithm time/sublime. Example: Log₂ 8 = 3; this means that to get to 8 on a binary search we will need three tries (2^3=8).
Quadratic Runtime. This is presented as O(n²). This is an operation raised to the power of two.
Cubic Runtime. This is a runtime raised to the power of three; n^3.
Polynomial Runtime is all the runtime where we look at the worst-case scenario, O(n^k).
Exponential algorithm: These are expensive methods/algorithms presented as O(xⁿ). These are algorithms that are inefficient because one change causes a significant change in the output. Such methods include:
- Brute Force
- Travelling Salesman
Top comments (1)