Big O Notation - True or False

The aim of the Big-O notation is to give a rough idea of how time and/or memory requirements will grow as the problem gets bigger.

• True

• False

Answer explanation

True. It measure time complexity or space complexity

The statement "The worst case run-time complexity of algorithm A is O(n²)" means that "Algorithm A takes at most c x n² steps (where c is a constant) to solve a problem of size n (for large n)"

• True

• False

Answer explanation

True (approximately) – it may not be true for small values of n, when a term in n and a constant may be significant.

Problems of complexity O(1) have only one statement, however large the problem.

• True

• False

Answer explanation

False – there may be any number of statements but the number stays constant however large the problem becomes.

A problem with complexity O(100n) is of a different order of magnitude from one of complexity O(n).

• True

• False

Answer explanation

False – the constant coefficient of n is irrelevant and is ignored.

An algorithm of complexity O(n³) is useless for any practical purpose.

• True

• False

Answer explanation

False – problems that grow in polynomial time are not considered insoluble or “intractable”.

Hashing is an example of a problem of time complexity O(1).

• True

• False

Answer explanation

True – however many values are to be hashed, the time taken to execute the hashing algorithm remains constant.

Some problems may be O(n) for small values of n but O(n²) for large values of n.

• True

• False

Answer explanation

False – the time complexity does not change.

"Divide and conquer" algorithms typically have time complexity O(log n) and are very efficient.

• True

• False