CODEWITHSUNDEEP
algorithmdata-structuresbig-otime-complexity
user3194626
user3194626

Reputation: 31

How do you work out the worst case time complexity of a function

So if we have a question like this How do we work it out:

What is the worst case time complexity of the method below (where n is array.length):

boolean search(int[] array, int value) {
  for (int j = 0; j < array.length; i++)
    if (array[j] == value)
      return true;
  return false;
}

Upvotes: 2

Views: 302

Answers (3)

Jebathon
Jebathon

Reputation: 4561

The worst case would be when the index of the value you are looking for is at the end of the array

So in this case it would be O(arraylength-1) since the position of the index is dependent on the time of search. Or O(n). If you can find it

http://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities

Upvotes: 1

barak manos
barak manos

Reputation: 30136

In the worst case, array does not contain value, and the total running time will be O(n).

Upvotes: 0

Simeon Visser
Simeon Visser

Reputation: 122346

In this case you can look at the structure of the code and reason as follows:

I can see that for (int j = 0; j < array.length; j++) means that j takes on the values from 0 to array.length - 1. So that means this is a linear loop with regard to the length of the array. The operations inside and below the loop happen in constant time.

So the question now is: what is the worst case? The worst case scenario is that the element is not found in the array at all, which means you're iterating over the entire array. Hence the algorithm is O(n) in worst case.

Upvotes: 6

Related Questions