Does randomness buy us anything inside P?
Problem: An array $A[1..2n]$ consists of $n$ 1s and $n$ 0s. Find an $i$ such that $A[i]$ is 1. 

You are allowed to query 'Which number is present in $A[i]$'? Each query takes constant time. 

Solution: 
Randomized Algorithm: Pick a random index $i$ and check if $A[i]$ is 1. Expected number of queries is 2, but any deterministic algorithm must make at least $n$ queries. Therefore, the randomized upper bound is strictly better than the deterministic lower bound in this model.

This is an example from query complexity which Tsuyoshi was referring to in the comment.