Big O Notation Flashcards Preview

Paper 1 - Computer Science > Big O Notation > Flashcards

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

Why is the base (as in n in logn(a)) not specified?

It is not specified because it is irrelevant to the time complexity, being a constant factor)