Flashcards in Big O Notation Deck (20)

Loading flashcards...

1

## What is time complexity?

### How much time an algorithm needs to solve a particular problem.

2

## How do we determine the efficiency of an algorithm (in terms of execution time)? / How do we determine the time complexity of an algorithm?

### By quantifying the number of basic operations the algorithm needs to execute

3

## What is the time complexity for an algorithm with a total of n+1 operations?

### The time complexity = n

4

## What can the order of magnitude/time complexity of an algorithm be expressed as?

### It can be expressed as a function of its size

5

## What does a function do?

### It maps one set of values onto another set of values

6

## How is a linear function expressed?

### f(x) = ax + c

7

## How is a polynomial function expressed?

### f(x) = ax^m + bx + c

8

## How is an exponential function expressed?

### f(x) = ab^x

9

## How is an logarithmic function expressed?

### f(x) = (a)logn(x)

10

## What is the permutation of a set of objects?

### The number of ways of arranging the objects.

11

## What is the formula for calculating the number of permutations?

### n! (factorial)

12

## What does Big O Notation express?

### -It expresses the time complexity of an algorithm

13

## What does O(1) describe?

###
An algorithm that takes constant time (the same amount of time) to execute regardless of the size of the input data set.

For example: suppose array a has n items:

length = len(a)

14

## What does O(n) describe?

### O(n) describes an algorithm whose performance will grow in linear time, in direct proportion to the size of the data set.

15

## What does O(n^2) describe?

### O(n^2) describes an algorithm whose performance is directly proportional to the square of the size of the dataset. It grows in polynomial time.

16

## What does O(2^n) describe?

### O(2^n) describes an algorithm where the execute time will double with every additional item added to the data set. It grows in exponential time.

17

## What does O(logn) describe?

### O(logn) describes an algorithm where the execute time that will grow very slowly as the size of the data set increases.

18

## What does O(n!) describe?

### O(n!) describes an algorithm where the execute time will grow very quickly. Faster than O(2^n)

19

## What has a time complexity of O(logn)?

### A binary search.

20