Searching for a number in an array is said to have a runtime of O(n) because there may be cases where the number doesn't exist in the array. In such cases, you'd have to have gone through the entire array, which is O(n).But how about in the case where we know the number definately exists in the array? Does the runtime change then?Also is there a way to find out the average number of searches it would have to do before a number is found in an array based on its size?
Runtime of searching for a number in an array?
algorithms;algorithm analysis;runtime analysis;search algorithms;arrays