Suppose that a divide and conquer algorithm solves a problem of size n by solving 3 sub-problems each of size 1/3 of the original, the divide step takes time O(n), the combine step takes time O(n2). Furthermore the base case, when n10, can be solved in constant time.

What is the recurrence for this algorithm?

Group of answer choices

T(n)=3T(n3)+O(n)+O(n2),n>10;T(n)=O(1),n10

T(n)=T(n3)+O(n),n>10;T(n)=O(1),n10

T(n)=3T(n3)+O(n2),n>1;T(n)=O(1),n=1

T(n)=3T(n3),n>1;T(1)=O(1)

T(n)=3T(13)+O(n)+O(n2),n>1;T(1)=O(1)