The running time $f(n)$ of such an algorithm can't depend just on $n$. It doesn't matter how big $f(n)$ is, there is always a state $|\psi\rangle$ which is very close to the boundary of the set of entangled states. For such a state your algorithm won't be able to decide with the error less than  $1/3$. 

In such cases a modified problem is considered, which is called a weak membership problem. 

In this case the weak membership problem would ask if $|\psi\rangle$ is within the Euclidean distance $\beta > 0$ to the boundary of entangled states. 
So, the time bound would depend on $n$ and $\beta$. 

In general, for mixed states on $\mathbb{C}^N \otimes \mathbb{C}^M$ the separability problem is strongly NP-hard, which means the weak membership problem is NP-hard for $\beta\le 1/poly(N,M)$, see https://arxiv.org/abs/0810.4507.

But in your setting $|\psi\rangle$ is pure, which should simplify it. On the other hand, we know $|\psi\rangle$ only through an oracle, which makes the problem harder than what is described in https://arxiv.org/abs/0810.4507