Computer scienceAlgorithms and Data StructuresIntro to algorithms and data structuresUnderstanding algorithms and complexity analysis

Complexity cases and how to use them

Theory

Impostors in a table

Report a typo

Here is a part of a table consisting of the best, average, and worst cases for different abstract algorithms. Find algorithms that can't be true in any way.

Number of an algorithm	Best case	Average case	Worst case
1	$O(1)$	$O(n^2)$	$O(n \cdot log \: n)$
2	$O(n \cdot log \: n)$	$O(n)$	$O(n \cdot log \: n)$
3	$O(n^2)$	$O(n^2)$	$O(n^2)$
4	$O(n)$	$O(1)$	$O(n^2)$
5	$O(n \cdot log \: n)$	$O(n \cdot log \: n)$	$O(\infin)$

Hint: recall the hierarchy/order of complexities: $O(1) < O(n) < O(n \cdot log \: n) < O(n^2) < O(\infin)$ . Keep in mind that the task is to find the algorithms which deviate from this order.

Select one or more options from the list

___

Create a free account to access the full topic