Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Interview Prep Materials > Big O - Array Sorting Algorithms > Flashcards

Big O - Array Sorting Algorithms Flashcards

1
Q

What is the best time complexity of quicksort?

A

O(n log(n)) - bad

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is quicksort?

A

A divide and conquer algorithm where it divides the array into two smaller sub arrays. An index in each array is chosen as pivot, and the pivot compares itself to all the other entries so all smaller values are before it and all larger values are behind it. Recursively goes through each sub array (the one before and the one after the pivot position) and repeats.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is the average time complexity of quicksort?

A

O(n log(n)) - bad

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is the worst time complexity of quicksort?

A

O(n^2) - terrible

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is the worst space complexity of quicksort?

A

O(log(n)) - good

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is merge sort?

A

A comparison based divide and conquer algorithm, where the list is divided into sublists of one element, then compared with an adjacent list to merge the two lists until it is sorted. A new array needs to be allocated to store the sorted list.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is the best time complexity of merge sort?

A

O(n log(n)) - bad

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the average time complexity of merge sort?

A

O(n log(n)) - bad

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is the worst time complexity of merge sort?

A

O(n log(n)) - bad

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the worst space complexity of merge sort?

A

O(n) - okay

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is timsort?

A

An adaptive sorting algorithm designer by Tim Peters, where it identifies the longest “run” (sorted subarray) and chooses either insertion or merge sort.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is the best time complexity of timsort?

A

O(n) - great!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is the average time complexity of timsort?

A

O(n log(n)) - bad

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is the worst time complexity of timsort?

A

O(n log(n)) - bad

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is the worst space complexity of timsort?

A

O(n) - okay

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is heapsort?

A

The High-Level Idea

Heapsort is similar to selection sort—we’re repeatedly choosing the largest item and moving it to the end of our array. The main difference is that instead of scanning through the entire array to find the largest item, we convert the array into a max heap ↴ to speed things up.

Strengths
Fast. Heap sort runs in O(nlg⁡(n))O(n\lg(n))O(nlg(n)) time, which scales well as nnn grows. Unlike quicksort, there’s no worst-case O(n2)O(n^2)O(n2) complexity.
Space efficient. Heap sort takes O(1)O(1)O(1) space. That’s way better than merge sort’s O(n)O(n)O(n) overhead.

Weaknesses

Slow in practice. While the asymptotic complexity of heap sort makes it look faster than quicksort, in real systems heap sort is often slower. (Remember, nnn and 2n2n2n are both O(n)O(n)O(n), even though the first is twice as fast as the second. Heap sort’s O(nlg⁡(n))O(n\lg(n))O(nlg(n)) hides constant factors, but they still impact overall performance.)

Source: https://www.interviewcake.com/concept/java/heapsort

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is the best time complexity of heapsort?

A

O(n log(n)) - bad

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is the average time complexity of heapsort?

A

O(n log(n)) - bad

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is the worst time complexity of heapsort?

A

O(n log(n)) - bad

20
Q

What is the worst space complexity of heapsort?

A

O(1) - great since it is done in place

21
Q

What is bubble sort?

A

A simple algorithm that begins from the beginning of the list and compares adjacent pairs and swaps their position if not sorted. It repeatedly goes through the list, which grows shorter each time as the larger values get sorted to the end.

22
Q

What is the best time complexity of bubble sort?

A

O(n) - good, only needs to go through once

23
Q

What is the worst space complexity of bubble sort?

A

O(1) - great, done in place

24
Q

What is the average time complexity of bubble sort?

A

O(n^2) - horrible

25
Q

What is the worst time complexity of bubble sort?

A

O(n^2) - horrible

26
Q

What is the best time complexity of insertion sort?

A

O(n) - great

27
Q

What is the average time complexity of insertion sort?

A

O(n^2) - horrible

28
Q

What is the worst time complexity of insertion sort?

A

O(n^2) - horrible

29
Q

What is the worst space complexity of insertion sort?

A

O(1) - great, done in place

30
Q

What is selection sort?

A

How It Works

Selection sort works by selecting the smallest element from an unsorted array and moving it to the front.

Here’s how it’d work on this array:

We’ll scan through all the items (from left to right) to find the smallest one …

… and move it to the front.

Now, the first item is sorted, and the rest of the array is unsorted.

Repeat! We’ll look through all the unsorted items, find the smallest one, and swap it with the first unsorted item.

We can do this for the next-smallest item

Source: https://www.interviewcake.com/concept/java/selection-sort

31
Q

What is the best time complexity of selection sort?

A

O(n^2) - horrible

32
Q

What is the average time complexity of selection sort?

A

O(n^2) - horrible

33
Q

What is the worst time complexity of selection sort?

A

O(n^2) - horrible

34
Q

What is the worst space complexity of selection sort?

A

O(1) - great

35
Q

What is the best time complexity of bucket sort?

A

O(n + k), where K is number of buckets

36
Q

What is the average time complexity of bucket sort?

A

O(n + k), where K is number of buckets

37
Q

What is the worst time complexity of bucket sort?

A

O(n^2) - horrible

38
Q

What is the worst space complexity of bucket sort?

A

O(n) - okay

39
Q

What is radix sort?

A

A non-comparative sorting algorithm that sorts data with integer keys by grouping keys by individual digits that share the same significant digit position and value. Starts with 1s place, then 10s, then 100s, etc.

40
Q

What is the best time complexity of radix sort?

A

O(nk) - good, but k is variable

41
Q

What is the average time complexity of radix sort?

A

O(nk) - good, but k is variable

42
Q

What is the worst time complexity of radix sort?

A

O(nk) - good, but k is variable

43
Q

What is the worst space complexity of radix sort?

A

O(n+k)

44
Q

What is bucket sort?

A

A comparison sorting algorithm that sets up an array of empty buckets. It distributes the contents of the original array in the buckets. Each non empty bucket is sorted, then each bucket is visited in order and put back in the original array.

45
Q

What is insertion sort?

A

A super simple sorting algorithm where it removes one element from the list, finds where it belongs in the sorted list, and inserts it there. It can be performed online (as the list is being received). Good for short lists, bad for long ones.

Interview Prep Materials (10 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions