CODEWITHSUNDEEP
time-complexity
user2252786
user2252786

Reputation: 1635

Finding average time complexity

I have an integer array, and some x integer value. I need to loop over the array comparing if the current array value is equal to x. If so, the loop breaks.

The worst-case time complexity is W(n) = n (searched element is at the end of the array)
The best-case time complexity is B(n) = 1 (searched element is at the beginning of the array)

My question is - how do I find the average-case time complexity here?

As far as I know I have two possible cases - the element can be found in the array, and the element is not in there. But what's next? Do I have to count some probabilities? Or just simply say A(n) = n/2? What about the second case?

Upvotes: 2

Views: 7159

Answers (2)

user2471961
user2471961

Reputation:

Chances are incredibly high that this prompt wants you to use Big-O notation (you can look this up yourself).

The asymptotic average-case complexity when the element is or is not in the array is still O(n), because the /2 is a "constant factor" that is abstracted out of Big-O notation.

My conjecture is further given credence by the fact that you're not told how much time it takes to increment an index or compare two elements. You're already assuming that several things are "acceptable constants", so a /2 here or there does not change the asymptotic time complexity you are concerned with at all.

Upvotes: 1

Enigma
Enigma

Reputation: 1717

Average-case complexity when the element is in the array: 

A(n) = n / 2

Average-case complexity when the element is not in the array: 

A(n) = n

If the probability that the element is in the array is 0 <= p <= 1, then your average case complexity is: 

A(n) = p * (n / 2) + (1 - p) * n

Upvotes: 1

Related Questions