Question: Time complexity consider the Java methods: //assume a.length > 0 static int g(int [] a){ return g (a, 0, a.length-1); } static int g(int []
Time complexity
consider the Java methods:
//assume a.length > 0 static int g(int [] a){ return g (a, 0, a.length-1); }
static int g(int [] a, int i, int j) { if (i == j) return a[i]; int onefourth = (j+1-i) /4; return g(a, i, i+onefourth) + g(a, i+onefourth+1, j); }
(a) what is the asymptotic time complexity of the algorithm described by g(int[]) in function of the input's length. explain with arguments why.
(b) how would the algorithm cost change if you would assign (j+1-i)/5 to the variable onefourth instead of (j+1-i)/4 ?
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
