Prev Next

DataStructures / Data structures Interview questions

How insertion sort is faster than bubble sort?

In bubble sort at i-th iteration you have n-i-1 inner iterations ((n^2)/2), but in insertion sort you have maximum i iterations on i-th step, but i/2 on average, as you can stop inner loop earlier, after you found correct position for the current element. So you have (sum from 0 to n) / 2 which is (n^2) / 4.

❤Cash Back At Stores you Love !!!❤

Earn your $10 reward when you make your first purchase through Ebates by signing up with clicking below button.

Ebates Coupons and Cash Back

More Related questions...

What is data structure? Define linear data structure. Define Non-Linear data structure. Mention different data structures. What are the operations that can be performed on a data-structure? What is an Array? Define Linked list. What are the different types of linked list? How do I find middle element of linked list? Define Stack in data structures. Explain queue in data structure. Why do we need stack data structure? Minimum number of queues needed to implement the priority queue. Applications of tree data-structure. What is priority queue? What is the difference between Stack and Queue data structure? Difference between Singly Linked List and Doubly Linked List data structure What is binary search tree? List out few areas in which data structures are applied extensively? What is recursive data structure? Give few examples of mathematical function that can be performed recursively? Is sorting possible with delete operation in data structure? List out few applications that make use of Multilinked Structures? In RDBMS, what is the efficient data structure used in the internal storage representation? Describe binary tree and its property. What are multidimensional arrays? Are linked lists considered linear or non-linear data structure? What is dynamic data structure? Differentiate Stack and Array. What is a dequeue? What is a graph? What is an AVL tree? What operations can be performed on stack data structure? What is linear search? Explain binary search. What is heterogeneous linked list? Which data structures are used with the following areas: RDBMS, Network data model and hierarchical data model? What is a postfix expression? What is a spanning Tree? What does a linked list node consist of? What are the different types of binary tree? What is tree traversal? What is a minimum spanning tree (MST) ? What is hashing? What is algorithm? What is the time complexity of Algorithm? Explain asymptotic analysis of an algorithm? Mention the criteria for algorithmic analysis. Explain Quick Sort algorithm. Explain bubble sort algorithm. How insertion sort algorithm works? Explain selection sort algorithm. Explain merge sort algorithm. What is shell sort? How quick sort works? What is recursive function? What is Huffmans algorithm? Which algorithm used in solving the 8 Queens problem. Difference between a Tree and Graph in Data structure. Explain Heap data structure. Explain max heap data structure. Explain min heap data structure. Difference between Binary tree and Binary search tree. Define a complete Graph. What is Adjacency matrix? Difference between undirected and Directed graph. What is a digraph in data structures? Explain Adjacency list in data structures. What is Incidence matrix? What is a dense graph? What is a sparse graph? Preferred way of representing the graph. What is a non-simple graph? Explain Knapsack problem. What is Dynamic programming? Difference between memoization and dynamic programming. How insertion sort is faster than bubble sort? Explain trie data structure. What is edge case in algorithm evaluation? How to represent complexity when the best case, average case, and worst case are equal? How do I delete an element from heap data structure? What is depth of node in a tree. How to find the height of a node in a tree? What is a strict or proper binary tree? Define complete and perfect binary tree. Difference between Insertion Sort and Selection Sort. What is the complexity of Merge sort algorithm? What is inverted binary tree? Explain jagged array.
Show more question and Answers...

System Design

Comments & Discussions