Test 1 Flashcards

1
Q

O(n)

A

denotes that the function has the same or lower rate of growth than n

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

Ω(n)

A

denotes that the function has the same or quicker rate of growth than n

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

Θ(n)

A

denotes that the function has the same rate of growth as n

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

stack-empty complexity

A

O(1)

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

stack push complexity

A

O(1)

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

stack pop complexity

A

O(1)

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

enqueue complexity

A

O(1)

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

dequeue complexity

A

O(1)

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

list-search

A

O(n)

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

list-insert

A

O(1)

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

list-delete

A

O(1)

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

root

A

top element of the tree; element with no parents

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

external node; leaf

A

a node with no children

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

internal node

A

a node with at least one child

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

tree depth

A

distance from root to a node

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

tree height

A

distance from root to lowest node

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

preorder, postorder, or inorder traversal complexity

A

O(n)

18
Q

preorder traversal

A

traversal in which a node is visited before its descendants

19
Q

postorder traversal

A

traversal in which a node is visited after its descendants

20
Q

inorder traversal

A

traversal in which a node is visited after its left subtree and before its right subtree

21
Q

euler tour traversal

A

a traversal that walks around the entire tree and has preorder, postorder, and inorder traversal as special cases.

22
Q

insertion sort average performance

A

O(n^2)

23
Q

quick sort average performance

A

O(n log(n))

24
Q

merge sort average performance

A

O(n log(n))

25
Q

selection sort average performance

A

O(n^2)

26
Q

counting sort average performance

A

O(n+r)

27
Q

radix sort average performance

A

O(n * k/d)

28
Q

heap

A

a nearly complete binary tree in which each node has a value > its parents value

29
Q

max-heap-insert

A

O(log(n))

30
Q

heap-extract

A

O(log(n))

31
Q

max-heapify

A

O(log(n)

32
Q

build-max-heap

A

O(n)

33
Q

heap sort

A

O(n log(n))

34
Q

chaining

A

a collision-handling strategy in which each entry in the array contains a linked list

35
Q

linear probing

A

a collision-handling strategy in which the colliding entry goes to the next linearly available index.

36
Q

double hashing

A

a collision-handling strategy in which the colliding entry gets a secondary hash function to find another index.

37
Q

binary search performance

A

O(log n)

38
Q

BST Tree Insert

A

O(h)

39
Q

BST Tree Delete

A

O(h)

40
Q

RBT Tree Insert

A

O(log n)

41
Q

RBT Tree Delete

A

O(log n)