Arrays, InsertionSort, BigO

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/22

encourage image

There's no tags or description

Looks like no tags are added yet.

23 Terms

1
New cards

Array

A data structure that stores a fixed-size sequence of elements of the same data type in contiguous memory locations.

2
New cards

Indexing

Accessing elements in an array via an index, typically starting at index 0.

3
New cards

Fixed Size

The size of an array cannot be changed once it is created.

4
New cards

Access Time Complexity

O(1) for accessing elements by index in an array.

5
New cards

Insertion/Deletion at End

O(1) time complexity for inserting or deleting elements at the end of an array.

6
New cards

Insertion/Deletion at Beginning or Middle

O(n) time complexity for inserting or deleting elements at the beginning or middle of an array.

7
New cards

Traversal

The process of iterating through all elements in an array.

8
New cards

Searching

Finding an element in an array using linear search (O(n)) or binary search (O(log n)) if sorted.

9
New cards

Sorting

The process of arranging elements in an array using algorithms like Insertion Sort.

10
New cards

Insertion Sort

A simple comparison-based sorting algorithm that builds a sorted array one element at a time.

11
New cards

Steps of Insertion Sort

Start with the second element, compare, shift elements, and insert the current element in the correct position.

12
New cards

Best Case Time Complexity for Insertion Sort

O(n) when the array is already sorted.

13
New cards

Average/Worst Case Time Complexity for Insertion Sort

O(n²) when the array is sorted in reverse order.

14
New cards

Space Complexity of Insertion Sort

O(1) as it is an in-place sorting algorithm.

15
New cards

Stability of Insertion Sort

Yes, it preserves the relative order of equal elements.

16
New cards

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).

17
New cards

O(1)

Constant time complexity where the operation's time remains constant regardless of input size.

18
New cards

O(log n)

Logarithmic time complexity, often occurring in algorithms that halve the problem size at each step.

19
New cards

O(n)

Linear time complexity where the operation's time increases linearly with input size.

20
New cards

O(n log n)

Log-linear time complexity, common in efficient sorting algorithms like merge sort and quicksort.

21
New cards

O(n²)

Quadratic time complexity, typical in algorithms with nested loops over the input.

22
New cards

O(2ⁿ)

Exponential time complexity, common in algorithms that try all possible solutions.

23
New cards

O(n!)

Factorial time complexity, typical in algorithms generating all possible permutations of the input.