Big O Flashcards

You may prefer our related Brainscape-certified flashcards:
1
Q

Complexity

A

how well the performance of an algorithm scales as the size of data sets increase.

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

time complexity

A

the number of steps/line of code executed in an algorithm.

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

space complexity

A

the memory requirement for an algorithm

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

efficiency

A

time complexity and space complexity

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

BigO

A

a complexity notation. remove all coefficiants and just write the value of n with the largest exponent e.g. O(n)

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

O(1)

A

constant complexity

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

constant complexity

A

An algorithm that always executes in the same time regardless of the size of the data set. Efficient with any data set.

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

O(log n)

A

Logarithmic Complexity

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

Logarithmic Complexity

A

An algorithm that halves the data set in each pass. Efficient with large data sets. Good algorithms.

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

O(n)

A

Linear Complexity

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

Linear Complexity

A

An algorithm whose performance is proportional to the size of the data set and declines as the data set grows. Fair algorithms.

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

O(n^a)

A

Polynomial complexity (quadratic, cubic etc)

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

Polynomial complexity (quadratic, cubic etc)

A

An algorithm whose performance is proportional to the square of the size of the data set. Significantly reduces efficiency with increasingly large data sets. Poor algorithms.

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

O(2^n)

A

Exponential Complexity

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

Exponential Complexity

A

An algorithm that doubles with each addition to the data set in each pass. Inefficient. Extremely poor algorithms that should be avoided.

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

O(n log N)

A

Algorithms that divide a data set but can be solved using concurrency on independent divided lists.

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

complexity order

A

O(1) -> O(logn) -> O(n) -> O(nlogN) -> O(n^2) -> O(2^n)

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

Linear search best

A

O(1)

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

linear search average

A

O(n)

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

linear search worst

A

O(n)

21
Q

binary search best

A

O(1)

22
Q

binary search average

A

O(logn)

23
Q

binary search worst

A

O(logn)

24
Q

Binary search tree best

A

O(1)

25
Q

Binary search tree average

A

O(logn)

26
Q

Binary search tree worst

A

O(n)

27
Q

Hashing best

A

O(1)

28
Q

HAshing average

A

O(1)

29
Q

Hashing worst

A

O(n)

30
Q

Breadth/Depth first best

A

O(1)

31
Q

Breadth/Depth first average

A

O(V+E)
V = no. vertices
E = no edges

32
Q

Breadth/Depth first worst

A

O(V^2)

33
Q

Bubble sort best

A

O(n)

34
Q

Bubble sort average

A

O(n^2)

35
Q

Bubble sort worst

A

O(n^2)

36
Q

Bubble sort space complexity

A

O(1)

37
Q

Insertion sort Best

A

O(n)

38
Q

Insertion sort Average

A

O(n^2)

39
Q

Insertion sort Worst

A

O(n^2)

40
Q

Insertion sort Space complexity

A

O(1)

41
Q

Merge sort best

A

O(nlogn)

42
Q

Merge sort average

A

O(nlogn)

43
Q

Merge sort worst

A

O(nlogn)

44
Q

Merge sort Space complexity

A

O(n)

45
Q

Quick Sort best

A

O(nlogn)

46
Q

Quick Sort average

A

O(nlogn)

47
Q

Quick Sort Worst

A

O(n^2)

48
Q

Quick sort space complexity

A

O(logn)