A problem of size n requires n² bit operations. What is the largest size instance that can be solved in 1 second, if each bit operation is carried out in 10⁻⁹ second?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. 3.16×10⁴
Explanation
The time to solve an instance of size n is n² × 10⁻⁹ seconds, so solving it within 1 second requires n² × 10⁻⁹ ≤ 1, i.e. n² ≤ 10⁹. Taking the square root of both sides gives n ≤ √(10⁹) = √10 × 10⁴ ≈ 3.1623 × 10⁴. So the largest instance size solvable in 1 second is approximately 3.16×10⁴.More Data Structures and Algorithms questions
- If f(n) = θ(g(n)) and g(n) = O(h(n)), then which of the following is true?
- The number of leaf nodes in a full 4-ary rooted tree of n nodes is
- Which of the following statements maybe false for a decision problem X ∈ NP?
- A binary search tree is obtained by inserting the words "Mathematics", "Physics", "Geography", "Zoology", "Metrology", "Geology", "Psycholo…
- In open addressing, how are collisions typically resolved?
- What is the height of the binary search tree obtained by inserting the numbers 40, 60, 50, 37, 52, 15, 8, 22 in the given order