Brainscape's Knowledge GenomeTM

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


See full index

Data Structures & Algorithms > Big O Notation > Flashcards

Big O Notation Flashcards

1
Q

What do O and n stand for in Big O Notation?

A

O: “order of the functions” “operarations”

n: “the size of the dataset”

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

What are the common functions for data structures?

A

access, search

insert, delete

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

What is the most common space complexity?

A

O(n)

linear time

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

What is the space complexity for a Skip List?

A

O(n log n)

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

What is constant time?

A

O(1)

An operation that takes the same amount of time, no matter the size of the dataset

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

What is linear time?

A

O(n)

An operation where time increases as size increases

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

What is logarithmic time?

A

O(log n)

An operation that decreases the size of the dataset each iteration

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

What is quadratic|polynomial time?

A

O(n^2)

An operation that runs more than one loop (nested loops)

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

What is exponential time?

A

O(2^n)

An operation that has multiple permutations for each input

“Brute Force” algorithms

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

What are the time complexities? Rate them fastest to slowest.

A 
Constant O(1) fastest
Logarithmic O(log n) fast for large datasets
Linear O(n) fast for small datasets
O(n log n) slower than linear
Quadratic O(n^2) slower as data grows
Exponential O(2^n) very slow
Factorial O(n!) Slowest
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What are the time complexities of access & search for stacks, queues, and linked-lists?

A

Both are linear time O(n)

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

What are the time complexities of insert & delete for stacks and queues?

A

Both are constant time O(1)

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

What are the time complexities of an array?

A

Access O(1) constant time

Search O(n) linear time
Insertion O(n)
Deletion O(n)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What are the time complexities of
access, search, insert, delete for
B-tree, Red-Black-tree, & AVL-tree?

A

All are logarithmic time O(log n)

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

What is the time complexity of quicksort?

Space complexity?

A

Worst: O(n^2) quadratic
Can be O(n log n)

Space: O(log n)

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

What is the time complexity of mergesort?

Space complexity?

A

Time O(n log n)

Space O(n) linear

17
Q

What is the time complexity of timesort?

Space complexity?

A

Time: O(n log n)

Space: O(n) linear

18
Q

What is the time complexity of heap sort?

Space complexity?

A

Time: O(n log n)

Space: O(1)

19
Q

What are the time and space complexities of bubble, insertion, and selection sort?

A

Time: O(n^2) quadratic

Space O(1)

20
Q

What is an “in-place” algorithm?

A

An algorithm that transforms its input and uses no auxiliary data structure

21
Q

What is a pointer?

A

An object that stores a memory address

A pointer references a location in memory

22
Q

What are the pros and cons of an in-place algorithm

A

Pro: it is very time efficient

Con: it mutates the original data structure

23
Q

What are the time complexities for a hash table?

A 
search, insert, delete:
Worst O(n) linear
Best O(1) constant
24
Q

What are the time complexities for a skip list, binary search tree, and KD tree?

A

access, search, insertion, delete:
Worst: O(n)
Best: O(log n)

25
Q

What are the time complexities of a splay tree?

A 
search, insert, delete:
Always O(log n)
26
Q

What arenthe time complexities of a Cartesian Tree?

A

search, insert, delete:
Worst: O(n)
Best: O(log n)

27
Q

What is accessing a data structure?

A

access:

When you use the element’s index|address to get the value

28
Q

What is searching a data structure?

A

Searching is iterating/traversing the data structure to find the element you are looking for

29
Q

What is insertion?

A

Adding an element to a data structure

30
Q

What is deletion?

A

Removing an element from a data structure

31
Q

What is Amortized Time?

A

Essentially amortized time means “average time taken per operation, if you do many operations”.

If you do an operation a million times, you don’t really care about the worst-case or the best-case of that operation.

What you care about is how much time is taken in total when you repeat the operation a million times.

Data Structures & Algorithms (15 decks)

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