Time Complexity of Basic functions in Python

When working on programs that deal with large amounts of data, optimization becomes very important. The slightest change in the implementation of any workflow could drastically affect the time required by the program. To calculate the time taken to run a program, we need to know the time complexity of algorithms and functions that we are using in the program.

 Here let's have a look at the time complexities of some commonly used functions in Python which are li
  1. sort()
  2. 'in' or 'obj.__contains__(ele)
  3. Retrieving an element present at a given index.

Time Complexity of Sort() function:

Python implements Timsort in its sort() function. Timsort is a hybrid of Insertion Sort and Merge sort which proves to be more efficient in real-life scenarios. It basically utilizes the efficiency of Insertion sort on smaller lists by
  1. Breaking down a huge list into smaller parts 
  2. Performing Insertion sort on the smaller parts and
  3. Performing merge sort on those sorted parts.
This method is very efficient that traditional Merge sort or Insertion Sort.
Worst Case Time Complexity: O(n log n) Case Average Case Time Complexity: O(n log n) 
Best Case Time Complexity: O(n)
Space Complexity: n

Time Complexity of 'in' keyword:

The 'in' keyword is used to tell if a given element is present in a list/tuple/set or any iterable and to traverse along an iterable. Using this keyword is essentially calling l.__contains__(ele), where 'l' is the object of an iterable class and 'ele; is the element we are looking for. 

The complexity of the keyword(or function) is entirely dependent on the iterable or the object on which the operation. Let us have a look at the time complexities of preforming this operation on different iterables/objects.

List: 
    Average Case - O(1)

Set:
    Average Case - O(1)
    Worst Case - O(n)

Dict:
     Average Case - O(1)
     Worst Case - O(n)
      
You can see the complete list of time complexities of different functions here.  

Retrieving an element present at a given index:

Just like searching, retrieving an element from a given index is dependent on the iterable from which we are retrieving the element.

Retrieving an element from a list at a given index can be done at O(1) in all cases. This is contrary to popular belief which states that the time required to retrieve an element increases as the element goes deeper into the list. This is because the Implementation of Lists in Python is done as dynamic arrays instead of standard linked lists. This allows us to retrieve elements from lists from any given index at O(1) complexity.
The time complexity of accessing elements at a given index for Sets and Dictionaries are O(1) as well.



I'm Faihan, a Computer Science & Engineering Student who has an endless enthusiasm towards Programming and latest Technologies.

Comments

Post a Comment

Popular posts from this blog

Variables in Python

Variables are containers that are used to store data. Python is a dynamically-typed language which means variables can store any type of data such as integers, float, strings, etc. Let us catch a glimpse of variables in this in detail. Declaring variables in Python: We might have seen in languages like C and Java where we have to define a variable with the type of data it will hold before assigning value to the variable. Unlike that, in Python, We don't have to explicitly define variables and their types. To create a variable, just type the name of the variable, use '=' sign, and assign a value.  a = 5 print(a)  The above code sets the value 5 to the variable 'a'. When you print a variable, the value associated with the variable will be printed. Thus the output for the above code will be 5. Just like that, variables can have any type of data. a = 5                b = 10.3            c =...
Read more

Lists in Python

Image
List in Python is a collection of similar/different data types. Defining a list: A List can be defined/created by enclosing the values within square brackets '[]'. l = [5,7,9,2,4] The above code will create a list with the values given inside the brackets. We can create an empty list by giving just nothing within those square brackets. l = [] Printing a list: We can print the list just by passing the list into the print() function. l = [5,7,9,2,4] print(l)  Output: [5,7,9,2,4]  Creating a list with predefined values: We can create a list with predefined values by using * operator on any list multiplied by n times. l = [0] * 5 print(l)  Output: [0,0,0,0,0] Accessing list elements: We can access the elements of a list by calling the list followed by the index value enclosed in square brackets. l = [5,7,9,2,4] print(l[2])  Output: 9 Since Indices of a list start with 0, Index 0 corresponds to the first element in the li...
Read more