# Big O Notation Flashcards Preview

## Paper 1 - Computer Science > Big O Notation > Flashcards

Flashcards in Big O Notation Deck (20)
1
Q

What is time complexity?

A

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

2
Q

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

A

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

3
Q

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

A

The time complexity = n

4
Q

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

A

It can be expressed as a function of its size

5
Q

What does a function do?

A

It maps one set of values onto another set of values

6
Q

How is a linear function expressed?

A

f(x) = ax + c

7
Q

How is a polynomial function expressed?

A

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

8
Q

How is an exponential function expressed?

A

f(x) = ab^x

9
Q

How is an logarithmic function expressed?

A

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

10
Q

What is the permutation of a set of objects?

A

The number of ways of arranging the objects.

11
Q

What is the formula for calculating the number of permutations?

A

n! (factorial)

12
Q

What does Big O Notation express?

A

-It expresses the time complexity of an algorithm

13
Q

What does O(1) describe?

A

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
Q

What does O(n) describe?

A

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

15
Q

What does O(n^2) describe?

A

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
Q

What does O(2^n) describe?

A

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
Q

What does O(logn) describe?

A

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

18
Q

What does O(n!) describe?

A

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

19
Q

What has a time complexity of O(logn)?

A

A binary search.

20
Q

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

A

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