Introduction to Data Science With Python
In this series, we’ll see time complexities expressed using the Big-O notation.
Each programmer should know how much it costs her/him writes code. Otherwise, there is no difference between a cat’s pressing random the keyboard.
Before start, don’t forget I’m a mortal too, so I can make mistakes. If something is wrong, please notify me.
Let’s see what is like algorithm analysis.
Constant Time O(1)
It means execution time always the same. For example;
def square(n):
return n**2The function of the above, returns the square of a given number(n). In this part, n size doesn’t important. Time complexity always the same. Now we see another example.
def is_int(n):
return isinstance(n, int)This function same like other one, it just returns boolean (True, False), by given number is int or not and given value’s size is not important. Time complexity is O(1).
Linear Time O(n)
Linear algorithm’s execution time depends on the size of n input. For example, we have two lists named a and b with lengths of 3 and 10, respectively.
> a = [“are”, “you”, “ok”]
> b = [4,1,2,3,6]If we want to find an index of an element in lists, their time complexity increases or decreases directly proportional to lengths.
We can show a linear search as the most common use.
In this example, if we are looking for “are”, the list will loop only once, but this is the best scenario, we should base always the worst scenario, and for the worst scenario, the word is “ok”. Loop visit all elements of the list and the cost is O(n). Let’s strengthen our knowledge with the following example
When we examine this example, as you can see we should visit all elements of the list. Because the list unordered and we’ll never know which is bigger than other unless checking one by one.
Logarithmic Time O(log n)
Let’s think about a list with have sorted numbers. We need to find an element’s index which is inside the list. For a scenario like this, binary_search comes to our mind.
What the flower this binary search? It’s basically “divide and conquer”. Binary search divides the list each loop, until finding the index. That collapse search area, and the possibility to find the element’s index bein much easier.
For Example
When we examine this example;
- Find the middle index in the list, and split list two-part into the middle. Now we have left and right list.
- We make a loop, it seems endless but it’s not.
- We have a breakpoint and for the reach breakpoint, our middle variable should equal our element’s index (Just a special situation, if our element left-part, we need to subtract 1 index.)
- Or “middle” variable lover than 1 or bigger length of the list.
Quadratic Time — O(n²)
For understanding quadratic time complexity, think you’re comparing 2 list’s elements each one another. That kind of complexities are seen mostly on sort algorithms.
For example, If we have 2 unordered lists and we need to find minimum combine
Or we can give another example use with bubble sort algorithm, I’m sure we’ll better understand it with an example.
Bubble sort, basically uses for sort an unsorted list.
As you can see, we need to compare all elements each other. In this scenerio worst case is O(n²)
Exponential Time — O(2^n)
I’m sure the best case to explain this complexity is Fibonacci numbers. Basically Fibonacci numbers start with 0 and 1 and the next number is the sum of two numbers before that number.
If you search on internet or somewhere, you’ll find Fibonacci numbers come from rabbits calculations :)
In this example, Fibonacci function calls until n=0 or 1. After that, the function collects returned numbers.
Another most popular algorithm is brute-force. This algorithm creates all possibilities with given data-set.
The general uses to try to find someone's passwords and make a cyber attack.
We’ll get help to itertools.permutations. If you examine python permutations function I’m sure you will understand better.
It’s my first article. I hope this topic will help you. I’m really avoiding cheating but of course, I got help from some articles. These are;
