We see algorithms used in pretty much every program that’s larger than a college project. These algorithms sometimes power necessary functionality inside these programs. That’s why it is essential to make sure that they are running efficiently. Even in situations where execution speed doesn’t matter much, it feels good to know that you are not coding a highly inefficient algorithm implementation. Before we begin this article, it is essential to note that memory usage is just as crucial as its runtime. I think this bites new programmers more often than speed inefficiencies because the consequences of exhausting system memory or using so much that there isn’t a reasonable amount left for other running processes can be fatal. By contrast, the only setback people suffer from a slow program is just time wasted waiting. Complexity and Big-O notation Runtime and memory usage are measured using a metric called portrayed in Big-O notation, simply the letter “O” followed by an expression in brackets. There are several different variants of Big-O, but by far, the representation is the most commonly used. Inside the parentheses is a variable such as , representing the input size to the algorithm. Of course, it is possible to use more than one variable inside the parentheses to define other factors and constants. complexity O n Specifically, means that the algorithm runtime or memory usage approaches units as the input size itself approaches infinity. The words used in the definition are very important. Big-O means that we equal an equal or shorter time or space measure at infinite input size. Little-O means the function time or space is strictly less than the complexity expression. While Big-Theta notation means it exactly equals the complexity. You might as see people using exclusively Big-O, but having three different expressions, each referring to , , and complexities. I think that’s an easier way to understand this concept. O(n) n n o(n) Θ(n) best case average worst-case For all the above, the measures of functions are still valid if the complexity expression is multiplied by an unknown constant, in other words. O-notation doesn’t care whether the complexity is or because the complexity in both cases increases honestly. n 30n This brings us to the complexity expressions themselves. Expressions Here are the complexities you will see most often with Big-O notation, with some examples of each: Constant: O(1) — Means the time or space is constant regardless of the input size, such as array access Logarithmic: O(log(n)) — The time/space is logarithmic with respect to the input size, such as binary search Linear: O(n) — The time/space is linear to the input size, such as iteration and linear search Linearithmic or Superlinear: O(n log(n)) — The time/space is linear multiplied by log(n) with respect to the input size, such as quicksort, mergesort, heapsort Quadratic: O(n**2) — The time/space is quadratic to the input size, i.e., for a given input size n the runtime or memory usage is squared. Insertion sort is an example of quadratic complexity. Cubic: O(n**3) — The time/space is cubic to the input size, such as Strassen’s Matrix Multiplication Exponential: O(2**n) — The time/space is exponential to the input size. Note that the 2 is a constant which any other number can replace. An example is the Traveling Salesman Problem Clearly, from the above list, you can see that exponential complexity is the worst possible runtime or space usage, while constant runtime is the best. Everyone wants to use algorithms that have constant complexity, but in most cases, this is not possible because there are no known implementations of those algorithms that have that simple complexity. Generally speaking, each algorithm has a minimum complexity which corresponds to the most efficient known implementation of that algorithm. So, that’s all about algorithmic complexity. Thanks for reading. Also published at https://medium.com/@zenul_abidin/algorithmic-complexity-basics-8c6a2aef54c2

Different

Read My Stories

Too Long; Didn't Read

In your car, at home, or at work — Bosch technology shapes many areas of life.

A Brief Introduction to Algorithmic Complexity

Too Long; Didn't Read

Company Mentioned

Ali Sherief

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

A Brief Introduction to Algorithmic Complexity

Too Long; Didn't Read

Company Mentioned

Ali Sherief

About Author

TOPICS

THIS ARTICLE WAS FEATURED IN...

RELATED STORIES