Big O Flashcards Preview

A-Level Computer Science OCR > Big O > Flashcards

Flashcards in Big O Deck (48)
Loading flashcards...
1

Complexity

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

2

time complexity

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

3

space complexity

the memory requirement for an algorithm

4

efficiency

time complexity and space complexity

5

BigO

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

6

O(1)

constant complexity

7

constant complexity

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

8

O(log n)

Logarithmic Complexity

9

Logarithmic Complexity

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

10

O(n)

Linear Complexity

11

Linear Complexity

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

12

O(n^a)

Polynomial complexity (quadratic, cubic etc)

13

Polynomial complexity (quadratic, cubic etc)

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

O(2^n)

Exponential Complexity

15

Exponential Complexity

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

16

O(n log N)

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

17

complexity order

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

18

Linear search best

O(1)

19

linear search average

O(n)

20

linear search worst

O(n)

21

binary search best

O(1)

22

binary search average

O(logn)

23

binary search worst

O(logn)

24

Binary search tree best

O(1)

25

Binary search tree average

O(logn)

26

Binary search tree worst

O(n)

27

Hashing best

O(1)

28

HAshing average

O(1)

29

Hashing worst

O(n)

30

Breadth/Depth first best

O(1)