139k views
5 votes
Which of the following would have a exponential Big O run-time complexity?

a. Efficiently find the definition of a given word in a dictionary
b. none of these
c. Find the largest value in an unsorted list
d. Determine if a binary number is even or odd
e. Find all duplicates in a list

User AllenJB
by
8.0k points

1 Answer

1 vote

Final answer:

The correct answer is 'b. none of these', as none of the listed options typically have an exponential Big O runtime complexity. Big O notation expresses algorithmic complexity, none of which applies to the options given.

Step-by-step explanation:

The question is asking which of the listed options would have an exponential Big O runtime complexity. The concept of Big O notation is used in computer science to describe the performance or complexity of an algorithm. Specifically, it is a way to express the worst-case scenario for how long an algorithm could take to complete as the size of the input data increases.

  • Efficiently finding the definition of a given word in a dictionary is typically done using a hash table or binary search, both of which have better than exponential complexity.
  • Finding the largest value in an unsorted list has a linear complexity, as it requires checking each element only once (O(n)).
  • Determining if a binary number is even or odd can be done in constant time by checking the last digit of the number (O(1)).
  • Finding all duplicates in a list can be done in O(n^2) in the worst case without extra space, or O(n) with additional space such as a hash table.

None of the options listed would typically have an exponential Big O runtime complexity, so the correct answer is 'b. none of these'.

User Mike Perrenoud
by
8.5k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.