We have already discussed several sorting algorithms that can sort n numbers in both O(n²) and O(nlogn) time complexity in the worst case. These algorithms determine the sorted order based only on the comparisons between the input elements. We call such sorting algorithms comparison sort, where we use only comparisons between elements to gain order information about an input sequence A, A, . . . , A[n-1]. In other words, given two elements A[i] and A[j], we perform one of the tests A[i] <= A[j], A[i] >= A[j], A[i] = A[j] to determine their relative order. Here we assume without loss of generality that all of the input elements are distinct.
We can visualize comparison sorts in terms of decision trees. A decision tree is a full binary tree structure that represents the comparisons performed by a sorting algorithm when it operates on an input of a given size. Here we only consider comparison operations and ignore other operations like control, data movement, etc.
Here is an example of a decision tree model for insertion sort operating on three elements. There are 3! = 6 possible permutations of the input elements, so the decision tree must have at least 6 leaves. Think!
Idea: Any decision tree that sorts n elements has a height always greater than nlogn.
Proof : Consider a decision tree of height h that sorts n elements. Since there are n! permutations of n elements, each permutation representing a distinct sorted order, the tree must have at least n! leaves. Another side, we know that the binary tree of height h has no more than 2^h leaves.
=> n! ≤ 2^h => h ≥ log(n!) From Stirling’s formula, n! > (n/e)^n => h ≥ log(n/e)^n => h ≥ n(log n — log e) => h ≥ nlogn — nloge => h > O(nlogn)
Therefore, any comparison-based sorting algorithm must make at least O(nlogn) comparisons to sort the input array.
There are sorting algorithms that run faster than O(nlogn) time complexity but they require special assumptions about the input sequence. These sorting algorithms use operations other than comparisons to determine the sorted order and work in O(n) time complexity.
Examples of sorting algorithms that run in linear time are counting sort, radix sort, bucket sort, etc. Counting sort and radix sort assume that the input consists of integers in a small range. Whereas, bucket sort assumes that the input is generated by a random process that distributes elements uniformly over the interval.
Reference: Algorithms by CLRS
Enjoy learning, Enjoy algorithms!
The code structure of a well-designed algorithm using data structure is just like a good house design. So learning algorithms require a good understanding of data structures properties, implementation techniques, and efficiency of critical operations. The fact is: Data Structures are the core building blocks of algorithms and real-life applications.
The concept of algorithm is essential for building high-performance software applications and cracking the coding interview to get a high-paying job in the software industry. So learning data structure and algorithms is one of the important career skills for programmers. Definition of the algorithm: An algorithm is a step-by-step procedure to transform a given input to the desired output and solve a computational problem.
Dynamic Programming is a popular problem-solving approach in data structures and algorithms, where we solve problems by combining the solutions to subproblems like the divide-and-conquer method. But rather than computing the same sub-problem repeatedly, we solve the sub-problem once and store the calculated value in extra memory to avoid the recomputation.
Level order traversal accesses nodes in level by level order. This is also called breadth-first search traversal or BFS traversal. Here we start from the root node and process it, then process all the nodes at the first level, then process all the nodes at the second level, and so on. In other words, we explore all nodes at the current level before moving on to the nodes at the next level.
Recursion means solving the problem via the solution of the smaller sub-problem. This blog will answer some critical questions like - what is recursion? What are its advantages and disadvantages? How do you identify recursion problems? What is the difference between recursion and iteration? etc.
Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops design and mathematics.