The Problem Given positive integers n, a, and b, determine T(n, a, b), the sum of all
Question:
The Problem Given positive integers n, a, and b, determine T(n, a, b), the sum of all multiples of a or b strictly less than n. Obviously, this can be done in O(n) time (because this is a numeric algorithm, this is actually exponential in the input size, which is actually log2(n)), as in the following pseudocode: 1: function Sum-Of-Multiples(n, a, b): Input A natural number n Output The sum of all multiples of a or b less than n 2: result 0 3: for i 1 to n 1 : 4: if a divides i or b divides i: 5: result result + i 6: return result In fact, this can be done in O(1) time, assuming that a single arithmetic operation takes O(1) time, regardless of the size of the operands.1 2 Writeup You must design an algorithm that determines T(n, a, b) in O(1) time prove its correctness and that its runtime is O(1) give pseudocode