CODEWITHSUNDEEP
javaalgorithmcomplexity-theory
Enzo
Enzo

Reputation: 316

Computation complexity of this simple algorithm

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;
}

Upvotes: 1

Views: 145

Answers (5)

Peter Lawrey
Peter Lawrey

Reputation: 533530

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)

Upvotes: 6

Анатолий
Анатолий

Reputation: 2857

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.

Upvotes: 1

partlov
partlov

Reputation: 14277

Because this is BOOLEAN array I thing average complexity would be constant O(1.5), worst O(n).

Upvotes: 0

Subhrajyoti Majumder
Subhrajyoti Majumder

Reputation: 41200

Average case would be O(n) as worst case because its array iteration.

Upvotes: 0

Renjith
Renjith

Reputation: 3274

Average case will also be O(n)

Upvotes: 0

Related Questions