1/22
Looks like no tags are added yet.
Array
A data structure that stores a fixed-size sequence of elements of the same data type in contiguous memory locations.
Indexing
Accessing elements in an array via an index, typically starting at index 0.
Fixed Size
The size of an array cannot be changed once it is created.
Access Time Complexity
O(1) for accessing elements by index in an array.
Insertion/Deletion at End
O(1) time complexity for inserting or deleting elements at the end of an array.
Insertion/Deletion at Beginning or Middle
O(n) time complexity for inserting or deleting elements at the beginning or middle of an array.
Traversal
The process of iterating through all elements in an array.
Searching
Finding an element in an array using linear search (O(n)) or binary search (O(log n)) if sorted.
Sorting
The process of arranging elements in an array using algorithms like Insertion Sort.
Insertion Sort
A simple comparison-based sorting algorithm that builds a sorted array one element at a time.
Steps of Insertion Sort
Start with the second element, compare, shift elements, and insert the current element in the correct position.
Best Case Time Complexity for Insertion Sort
O(n) when the array is already sorted.
Average/Worst Case Time Complexity for Insertion Sort
O(n²) when the array is sorted in reverse order.
Space Complexity of Insertion Sort
O(1) as it is an in-place sorting algorithm.
Stability of Insertion Sort
Yes, it preserves the relative order of equal elements.
Big O Notation
A mathematical notation that describes the upper bound of an algorithm's time or space complexity in terms of input size (n).
O(1)
Constant time complexity where the operation's time remains constant regardless of input size.
O(log n)
Logarithmic time complexity, often occurring in algorithms that halve the problem size at each step.
O(n)
Linear time complexity where the operation's time increases linearly with input size.
O(n log n)
Log-linear time complexity, common in efficient sorting algorithms like merge sort and quicksort.
O(n²)
Quadratic time complexity, typical in algorithms with nested loops over the input.
O(2ⁿ)
Exponential time complexity, common in algorithms that try all possible solutions.
O(n!)
Factorial time complexity, typical in algorithms generating all possible permutations of the input.