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