I calculate the optimal case complexity, average, and worst of this algorithm in java, I think if good is O (1) in the worst case is O (n), but I do not know if average! could you help me on how to calculate it? thank you!
public boolean searchFalse(boolean[] b){
boolean trovato=false;
for(int i=0;i<b.length;i++){
if(b[i]==false){
trovato=true;
break;
}
}return trovato;
}
I couldn't resist re-writing it
public boolean searchFalse(boolean[] bs){
for (boolean b : bs) if(!b) return true;
return false;
}
This stops after the first element potentially O(1).
If all the boolean are random the average search time is O(1) as you perform 2 searches on average, or if there is typically one false value in a random position the average is O(N)
If it has to search all the way, the worst case is O(N)
In short O(N/2) = O(N)
sum(i*(1/2)^i, i=1..infinity) the probability to have to look at exactly K booleans beeing (1/2)^K (ie, true K-1 times and then false).Complexity of algorithm is O(N).
If you need average amound of iterations it will be (1/1 + 1/2 + 1/4 +.. + 1/N) = (2 - 1/N) iterations expected if array with random booleans.
Average case will also be O(n)
Average case would be O(n) as worst case because its array iteration.
bs which always gives O(n) but here additional break may happen anywhere between 1-n or n/2 which becomes O(n/2) = O(n)Because this is BOOLEAN array I thing average complexity would be constant O(1.5), worst O(n).
