Big O Notation, Time Complexity | DSA Telusko

 

Big O Notation, Time Complexity | DSA

Telusko

Time Complexity and Algorithm Analysis

In this blog post, we will discuss time complexity and algorithm analysis. When building an application, we need to solve a problem, and that requires following a set of steps known as an algorithm. However, there can be multiple solutions to a problem, and we need to choose the best one. The best solution can be determined by considering factors such as memory usage and execution time, which are known as space complexity and time complexity, respectively. Algorithm analysis helps us analyze our algorithms and make them more efficient.

Linear Search and Binary Search

Let's focus on two algorithms: linear search and binary search. Linear search involves searching for an element in a sorted array by comparing each element one by one until the target element is found. However, the time complexity of linear search increases as the size of the array increases. On the other hand, binary search is a more efficient algorithm that works on a sorted array by repeatedly dividing the search interval in half until the target element is found.

Linear Search Pseudocode

procedure linearSearch(array, target):    length = length of array    for i in range(length):        if array[i] == target:            return i    return -1

The pseudocode above represents the linear search algorithm. It takes an array and a target element as input and searches for the target element by iterating through each element in the array. If the target element is found, the corresponding index is returned. If the target element is not found, -1 is returned.

Binary Search Pseudocode

procedure binarySearch(array, target):    left = 0    right = length of array - 1    while left <= right:        mid = (left + right) // 2        if array[mid] == target:            return mid        elif array[mid] < target:            left = mid + 1        else:            right = mid - 1    return -1

The pseudocode above represents the binary search algorithm. It takes a sorted array and a target element as input and searches for the target element by repeatedly dividing the search interval in half. If the target element is found, the corresponding index is returned. If the target element is not found, -1 is returned.

Let's say you have a sorted array with multiple values. In binary search, you divide the array into two parts and check if the value you are searching for matches the middle value. If it doesn't, you determine whether it is less than or greater than the middle value to decide which part of the array to focus on. By repeatedly dividing the array in half, you can quickly locate the desired value.

Here is the code for implementing binary search:

def binary_search(arr, target):    left = 0    right = len(arr) - 1        while left <= right:        mid = (left + right) // 2                if arr[mid] == target:            return mid        elif arr[mid] < target:            left = mid + 1        else:            right = mid - 1        return -1

The time complexity of binary search is logarithmic, meaning the running time increases slowly as the size of the input data grows. This makes it more efficient than linear search, especially for large arrays.