CODEWITHSUNDEEP
algorithmtime-complexitybig-o
Zanko
Zanko

Reputation: 4694

Running Time Complexity of O (n / 2)

I once understood this but not anymore. Lets say I have an algorithm that will return the number in the middle of an array.

for (int i = 0; i < nums.length; i++) {
  if (i == nums.length / 2) return nums[i];
}

The worst case of this will always be O (n / 2) right? There is no worse case than this. But how come we just conclude that it is O(n) ?

Upvotes: 8

Views: 19509

Answers (1)

Vality
Vality

Reputation: 6607

Big O time complexity is not about measuring the actual time an algorithm will take, it instead specifies what variables the time complexity is dependent on and what kind of relationship there is between those variables and the time complexity (ie linear, polynomial, exponential, etc).

Because constants do not effect the type of function the time complexity is they do not change the Big O value.

Note in your case the code you wrote may actually compile to something with constant time if the compiler is smart enough to note all iterations of the loop are dead but one.

Upvotes: 10

Related Questions