Question

Given the factorization of a number n, then the sum of divisors can be computed in _______

(a) linear time

(b) polynomial time

(c) O(logn)

(d) o(n+1)

I got this question in class test.

This intriguing question originated from Counting topic in section Counting of Discrete Mathematics

Answer 1

Correct choice is (b) polynomial time

To explain I would say: The exact number of running time depends on the computational model. When analyzing arithmetic with large numbers, we usually count either bit operations or arithmetic operations of size O(logn) (where n is the input size). Now, given the factorization of a number n, then the sum of divisors can be computed in polynomial time.