Determine if a string is a permutation of another string efficiently
You can establish a trivial lower bound of $\Omega(n)$, because you must at least observe all characters of each string (in worst case) to determine if they are permutations of each other. So $O(n)$ time complexity is the best you could do. 

Perhaps you could improve the space complexity though. Raphael describes a unique approach here to achieve constant space and linear time using properties of prime numbers.