Brainscape's Knowledge GenomeTM

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


See full index

Software Development Engineer Training > Big O Notations > Flashcards

Big O Notations Flashcards

1
Q

What are the Asymptotic Notation types?

A

Big O
Big Theta Θ
Big Omega Ω

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

What is the root meaning of Asymptotic?

A

The word asymptotic stems from the Greek root meaning “not falling together”. In ancient Greek mathematics the conic sections studied where deemed hyperbolas such as a graph where y = x and y = -x. The lines of both y values of x and -x curved lines on the graphs approach each other but never touch when x ➜ ∞.

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

O(1) space complexity denotes?

A

The amount of memory used is constant and is not dependent on data processing.

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

Which line on the graph represents constant time?

A

Line A (green line)

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

Which line represents logarithmic time complexity?

A

Line B (yellow line)

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

Which line represents linear time complexity?

A

Line c (blue line)

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

Which line represents quadratic time complexity?

A

Line d (red line)

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

Algorithms that are said to take the same amount of time executed are called?

A

Constant time algorithms

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

If the execution time of this algorithm is independent of the size of input, it is considered why type of complexity?

A

O(1) Constant Time

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

What type of complexity is an algorithm if the time to execute is directly proportional to the input size?

A

O(n) Linear Time Complexity

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

Binary search is an example of which time complexity?

A

O(log n) Logarithmic Time Complexity

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

What time complexity is the time it takes to run an algorithm is proportional to the logarithm of the input size n?

A

O(Log n) Logarithmic Time Complexity

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

What time complexity is an algorithm if the time to execution is proportional to the square of the input size?

A

O(n^2) Quadratic Time Complexity

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

Checking to see whether there are any duplicates in a deck of cards is an example of which time complexity?

A

O(n^2) Quadratic Time Complexity

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

Algorithms involving nested iterations such as nested loops are which type of time complexity?

A

O(n^2) Quadratic Time Complexity

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

Bubble sort is an example of which time complexity?

A

O(n^2) Quadratic Time Complexity

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

Selection sort is an example of which time complexity?

A

O(n^2) Quadratic Time Complexity

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

Insertion sort is an example of which time complexity?

A

O(n^2) Quadratic Time Complexity

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

Accessing arrays on average has which time and space complexity?

A

Time = Θ(1)
Space worst case = O(n)

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

Searching arrays, on average, has which time and space complexity?

A

Time average: Θ(n)
Space worst: O(n)

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

Array insertion, on average, has which time and space complexity?

A

Time average: Θ(n)
Space worst: O(n)

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

Array deletion, on average, has which time and space complexity?

A

Time average: Θ(n)
Space worst: O(n)

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

What is the best time complexity and the worst space complexity for array quicksort algorithms?

A

Time best: Ω(n log(n))
Space worst: O(log(n))

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

What is the best time complexity and the worst space complexity for array mergesort algorithms?

A

Time best: Ω(n log(n))
Space worst: O(n)

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

What is the best time complexity and the worst space complexity for array Timsort algorithms?

A

Time best: Ω(n)
Space worst: O(n)

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

What is the best time complexity and the worst space complexity for array heapsort algorithms?

A

Time best: Ω(n log(n))
Space worst: O(1)

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

What is the best time complexity and the worst space complexity for array bubble sort algorithms?

A

Time best: Ω(n)
Space worst: O(1)

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

What is the best time complexity and the worst space complexity for array insertion sort algorithms?

A

Time best: Ω(n)
Space worst: O(1)

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

What is the best time complexity and the worst space complexity for array selection sort algorithms?

A

Time best: Ω(n^2)
Space worst: O(1)

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

What is the best time complexity and the worst space complexity for array tree sort algorithms?

A

Time best: Ω(n log(n))
Space worst: O(n)

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

What is the best time complexity and the worst space complexity for array shell sort algorithms?

A

Time best: Ω(n log(n))
Space worst: O(1)

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

What is the best time complexity and the worst space complexity for array bucket sort algorithms?

A

Time best: Ω(n + k)
Space worst: O(n)

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

What is the best time complexity and the worst space complexity for array radix sort algorithms?

A

Time best: Ω(nk)
Space worst: O(n + k)

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

What is the best time complexity and the worst space complexity for array counting sort algorithms?

A

Time best: Ω(n + k)
Space worst: O(k)

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

What is the best time complexity and the worst space complexity for array cube sort algorithms?

A

Time best: Ω(n)
Space worst: O(n)

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

What is the average time complexity and the worst space complexity for stack access algorithms?

A

Time average: Θ(n)
Space worst: O(n)

37
Q

What is the average time complexity and the worst space complexity for Queue access algorithms?

A

Time average: Θ(n)
Space worst: O(n)

38
Q

What is the average time complexity and the worst space complexity for stack search algorithms?

A

Time average: Θ(n)
Space worst: O(n)

39
Q

What is the average time complexity and the worst space complexity for stack insertion algorithms?

A

Time average: Θ(1)
Space worst: O(n)

40
Q

What is the average time complexity and the worst space complexity for stack deletion algorithms?

A

Time average: Θ(1)
Space worst: O(n)

41
Q

What is the average time complexity and the worst space complexity for Queue insertion algorithms?

A

Time average: Θ(1)
Space worst: O(n)

42
Q

What is the average time complexity and the worst space complexity for Queue deletion algorithms?

A

Time average: Θ(1)
Space worst: O(n)

43
Q

What is the average time complexity and the worst space complexity for Singly-Linked Lists access algorithms?

A

Time average: Θ(n)
Space worst: O(n)

44
Q

What is the average time complexity and the worst space complexity for Doubly-Linked Lists access algorithms?

A

Time average: Θ(n)
Space worst: O(n)

45
Q

What is the average time complexity and the worst space complexity for Singly-Linked Lists search algorithms?

A

Time average: Θ(n)
Space worst: O(n)

46
Q

What is the average time complexity and the worst space complexity for Doubly-Linked Lists search algorithms?

A

Time average: Θ(n)
Space worst: O(n)

47
Q

What is the average time complexity and the worst space complexity for Singly-Linked Lists insertion algorithms?

A

Time average: Θ(1)
Space worst: O(n)

48
Q

What is the average time complexity and the worst space complexity for Doubly-Linked Lists insertion algorithms?

A

Time average: Θ(1)
Space worst: O(n)

49
Q

What is the average time complexity and the worst space complexity for Singly-Linked Lists deletion algorithms?

A

Time average: Θ(1)
Space worst: O(n)

50
Q

What is the average time complexity and the worst space complexity for Doubly-Linked Lists deletion algorithms?

A

Time average: Θ(1)
Space worst: O(n)

51
Q

What is the average time complexity and the worst space complexity for Skip List access algorithms?

A

Time average: Θ(log(n))
Space worst: O(n log(n))

52
Q

What is the average time complexity and the worst space complexity for Skip List search algorithms?

A

Time average: Θ(log(n))
Space worst: O(n log(n))

53
Q

What is the average time complexity and the worst space complexity for Skip List insertion algorithms?

A

Time average: Θ(log(n))
Space worst: O(n log(n))

54
Q

What is the average time complexity and the worst space complexity for Skip List deletion algorithms?

A

Time average: Θ(log(n))
Space worst: O(n log(n))

55
Q

What is the average time complexity and the worst space complexity for Hash Table search algorithms?

A

Time average: Θ(1)
Space worst: O(n)

56
Q

What is the average time complexity and the worst space complexity for Hash Table insertion algorithms?

A

Time average: Θ(1)
Space worst: O(n)

57
Q

What is the average time complexity and the worst space complexity for Hash Table deletion algorithms?

A

Time average: Θ(1)
Space worst: O(n)

58
Q

What is the average time complexity and the worst space complexity for Binary Search Tree access algorithms?

A

Time average: Θ(log (n))
Space worst: O(n)

59
Q

What is the average time complexity and the worst space complexity for Binary Search Tree search algorithms?

A

Time average: Θ(log (n))
Space worst: O(n)

60
Q

What is the average time complexity and the worst space complexity for Binary Search Tree deletion algorithms?

A

Time average: Θ(log (n))
Space worst: O(n)

61
Q

What is the average time complexity and the worst space complexity for Binary Search Tree insertion algorithms?

A

Time average: Θ(log (n))
Space worst: O(n)

62
Q

What is the average time complexity and the worst space complexity for Cartesian Tree search algorithms?

A

Time average: Θ(log (n))
Space worst: O(n)

63
Q

What is the average time complexity and the worst space complexity for B-Tree access algorithms?

A

Time average: Θ(log (n))
Space worst: O(n)

64
Q

What is the average time complexity and the worst space complexity for B-Tree search algorithms?

A

Time average: Θ(log (n))
Space worst: O(n)

65
Q

What is the average time complexity and the worst space complexity for Cartesian Tree insertion algorithms?

A

Time average: Θ(log (n))
Space worst: O(n)

66
Q

What is the average time complexity and the worst space complexity for Cartesian Tree deletion algorithms?

A

Time average: Θ(log (n))
Space worst: O(n)

67
Q

What is the average time complexity and the worst space complexity for B-Tree insertion algorithms?

A

Time average: Θ(log (n))
Space worst: O(n)

68
Q

What is the average time complexity and the worst space complexity for B-Tree deletion algorithms?

A

Time average: Θlog (n))
Space worst: O(n)

69
Q

What is the average time complexity and the worst space complexity for Red-Black Tree search algorithms?

A

Time average: Θ(log (n))
Space worst: O(n)

70
Q

What is the average time complexity and the worst space complexity for Red-Black Tree access algorithms?

A

Time average: Θ(log (n))
Space worst: O(n)

71
Q

What is the average time complexity and the worst space complexity for Red-Black Tree insertion algorithms?

A

Time average: Θ(log (n))
Space worst: O(n)

72
Q

What is the average time complexity and the worst space complexity for Red-Black Tree deletion algorithms?

A

Time average: Θ(log (n))
Space worst: O(n)

73
Q

What is the average time complexity and the worst space complexity for Splay Tree search algorithms?

A

Time average: Θ(log (n))
Space worst: O(n)

74
Q

What is the average time complexity and the worst space complexity for Splay Tree insertion algorithms?

A

Time average: Θ(log (n))
Space worst: O(n)

75
Q

What is the average time complexity and the worst space complexity for Splay Tree deletion algorithms?

A

Time average: Θ(log (n))
Space worst: O(n)

76
Q

What is the average time complexity and the worst space complexity for AVL Tree access algorithms?

A

Time average: Θ(log (n))
Space worst: O(n)

77
Q

What is the average time complexity and the worst space complexity for AVL Tree search algorithms?

A

Time average: Θ(log (n))
Space worst: O(n)

78
Q

What is the average time complexity and the worst space complexity for AVL Tree insertion algorithms?

A

Time average: Θ(log (n))
Space worst: O(n)

79
Q

What is the average time complexity and the worst space complexity for AVL Tree deletion algorithms?

A

Time average: Θ(log (n))
Space worst: O(n)

80
Q

What is the average time complexity and the worst space complexity for KD Tree access algorithms?

A

Time average: Θ(log (n))
Space worst: O(n)

81
Q

What is the average time complexity and the worst space complexity for KD Tree search algorithms?

A

Time average: Θ(log (n))
Space worst: O(n)

82
Q

What is the average time complexity and the worst space complexity for KD Tree insertion algorithms?

A

Time average: Θ(log (n))
Space worst: O(n)

83
Q

What is the average time complexity and the worst space complexity for KD Tree deletion algorithms?

A

Time average: Θ(log (n))
Space worst: O(n)

84
Q

What is the Big O time complexity when you have a loop within a loop?

a.) O(1)
b.) O(n^2)
c.) O(log n)
d.) O(n)

A

b.) O(n^2)

85
Q

How would the following be written: O(100n^2)

a.) O(100n)
b.) O(n^100)
c.) O(n^2)
d.) O(2n^100)

A

c.) O(n^2)

We drop the constant.

86
Q

What Big O is associated with Divide and Conquer?

a.) O(1)
b.) O(log n)
c.) O(n^2)
d.) O(n)

A

b.) O(log n)

O(log n) is divide and conquer.

87
Q

What is the correct way to write: O(n^2 + n) ?

a.) O(n^3)
b.) O(3n)
c.) O(n^2)
d.) O(n + n^2)

A

c.) O(n^2)

We drop the non-dominants.

88
Q

The most efficient Big O is:

a.) O(1)
b.) O(n^2)
c.) O(log n)
d.) O(n)

A

a.) O(1)

O(1) is known as constant time.

Software Development Engineer Training (4 decks)

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