Algorithm Efficiency CS Thinking Example 3

Follow the full solution, then compare it with the other examples linked below.

Example 3

hard
Rank these time complexities from most to least efficient: O(n2)O(n^2), O(1)O(1), O(nlog⁡n)O(n \log n), O(n)O(n), O(2n)O(2^n).

Solution

  1. 1
    Step 1: O(1)O(1) is constant — best. Then O(n)O(n) linear. Then O(nlog⁡n)O(n \log n). Then O(n2)O(n^2) quadratic. Then O(2n)O(2^n) exponential — worst.
  2. 2
    Step 2: Ranking: O(1)<O(n)<O(nlog⁡n)<O(n2)<O(2n)O(1) < O(n) < O(n \log n) < O(n^2) < O(2^n).

Answer

O(1),O(n),O(nlog⁡n),O(n2),O(2n)O(1), O(n), O(n \log n), O(n^2), O(2^n) — from most to least efficient.
Understanding the hierarchy of time complexities helps us evaluate and choose algorithms. Exponential algorithms become impractical very quickly as input grows.

About Algorithm Efficiency

The ratio of useful output energy (or power) to total input energy, expressed as a percentage — always less than 100% due to energy losses.

Learn more about Algorithm Efficiency →

More Algorithm Efficiency Examples

Example 1 hard

Algorithm A takes 100 steps for an input of size 10 and 400 steps for size 20. Algorithm B takes 10

Example 2 hard

Explain why binary search ([formula]) is more efficient than linear search ([formula]) for a sorted

Example 4 hard

Algorithm X checks every pair of students in a class of size `n`. Algorithm Y checks each student on

← All Algorithm Efficiency Examples Algorithm Efficiency Concept