# Big O Flashcards

1
Q

Complexity

A

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

2
Q

time complexity

A

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

3
Q

space complexity

A

the memory requirement for an algorithm

4
Q

efficiency

A

time complexity and space complexity

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)

6
Q

O(1)

A

constant complexity

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.

8
Q

O(log n)

A

Logarithmic Complexity

9
Q

Logarithmic Complexity

A

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

10
Q

O(n)

A

Linear Complexity

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.

12
Q

O(n^a)

A

13
Q

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.

14
Q

O(2^n)

A

Exponential Complexity

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.

16
Q

O(n log N)

A

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

17
Q

complexity order

A

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

18
Q

Linear search best

A

O(1)

19
Q

linear search average

A

O(n)

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

A

O(1)

31
Q

A

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

32
Q

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)