CODEWITHSUNDEEP
javaalgorithmcomplexity-theory
Enzo
Enzo

Reputation: 316

Complexity in cases excellent, average and bad

I created this method in java that indicates whether an integer array is sorted or not. What is its complexity? I think if good is O(1) in the worst case is O(n) in the average case?

static boolean order(int[] a){
  for(int i=0;i<a.length-1;i++){
    if(a[i]>a[i+1]) return false;
  }
 return true;
}

Upvotes: 2

Views: 123

Answers (2)

Mikita Belahlazau
Mikita Belahlazau

Reputation: 15434

You didn't tell anything about your input. So suppose it's totally random. So for any 2 neighbour pairs we have 50% chance that they are ordered. It means that we have probability 1 of making 1 step, 0.5 for 2 steps, 0.25 for 3 steps and generally 2^(-k) for k steps. Let's calculate expected number of steps:

enter image description here

I don't know how to calculate sum of this series so I used wolfram alpha and got answer: 2, so it's a constant.

So as I understand average case for random input is O(1).

I'm not sure it is correct way to calculate average complexity but seems fine to me.

Upvotes: 2

Qwerky
Qwerky

Reputation: 18455

Complexity is usually quoted in worst case, which in your case is O(n).

Upvotes: 0

Related Questions