3.4 Searching Algorithms/3.5 Sorting Algorithms

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

1/16

encourage image

There's no tags or description

Looks like no tags are added yet.

17 Terms

1
New cards

What are linear searches ideal for

Finding items in small data sets, searching unordered data (eg settings file), find-and-replace function in word processors

2
New cards

What are binary searches ideal for

Searching for items in large, sorted data sets, online dictionaries

3
New cards

Time complexity of linear search - BEST case

O(1) constant

4
New cards

Time complexity of linear search - AVERAGE/WORST case

O(n) linear

5
New cards

Time complexity of binary/binary tree search - BEST case

O(1) constant

6
New cards

Time complexity of binary search - AVERAGE/WORST case

O(log n) logarithmic

7
New cards

Time complexity of binary search tree - AVERAGE case

O(log n) logarithmic

8
New cards

Time complexity of binary search tree - WORST case

O(n) linear

9
New cards

Space complexity of linear search

O(1) constant

10
New cards

Space complexity of binary search

O(1) constant

11
New cards

What are bubble sorts ideal for

Very small data sets, situations when easy-to-program sorting algorithm is required

12
New cards

What are merge sorts ideal for

Larger data sets where memory is not a concern, parallel processing environments

13
New cards

Time complexity of bubble sort - BEST case

O(n) linear

14
New cards

Time complexity of merge sort - BEST/AVERAGE/WORST case

O(n log n) linearithmic

15
New cards

Time complexity of bubble sort - AVERAGE/WORST case

O(n2) polynomial

16
New cards

Space complexity of bubble sort

O(1) constant

17
New cards

Space complexity of merge sort

O(n) linear