Issue
I'm trying to calculate the time complexity of this code that sums the odd numbers of an array. I have done two methods and now I need to calculate the order complexity O(n)
This one is done by weak post-condition.
private static int sumaImparDebilit(int t[], int desde, int hasta) {
if (desde==hasta) {
if ((t[desde] % 2) == 1) {
return t[desde];
}
return 0;
}
if (t[desde]%2 == 1) {
return (t[desde] + sumaImparDebilit(t,(desde+1),hasta));
}
return (sumaImparDebilit(t,(desde+1),hasta));
}
This one is done by strong pre-condition.
private static int sumaImparFortalec(int t[], int hasta, int limite, int parcial) {
if (hasta <= limite) {
if ((t[hasta] % 2) == 1) {
return sumaImparFortalec(t,(hasta + 1),limite,(parcial + t[hasta]));
} else {
return sumaImparFortalec(t,(hasta + 1),limite,(parcial));
}
}
else {
return parcial;
}
}
Solution
I don’t know what you mean by “weak” and “strong” conditions, but both have time complexity O(n) and employ (for no good reason) recursion.
Surely this is simplest, and fastest:
int sum = 0;
for (int i = 0; i < t.length; i++)
if (t[i] % 2 == 1)
sum += t[i];
Answered By - Bohemian