This has puzzled me for a little. I start off with a list of primes that is sufficiently large. For my number $n$, I do trial division of primes in ascending order until I reach a prime that divides evenly, I factor out that prime from $n$, and I repeat until $n$ is prime.
Since there are no polynomial time algorithms, I guess something like $O((1+\epsilon)^n)$ where $\epsilon$ is some number, but I have really no background to go any further.
The algorithm isn't completely specified -- you say that you continue until the remaining number is prime, but not how you tell that this is the case. You use primes but don't explain how they are generated. You also don't say what you mean by time complexity. I will outline two versions of the algorithm and give the worst-case arithmetic complexity of each, assuming you can find the next prime instantly (via an oracle or the like).
First version: Stop once the current prime reaches the square root of the remaining number.
Second version: Whenever you find a prime, use a fast primality test like AKS (or, more practically, fastECPP) on the remaining part and stop if it is prime.
Both versions take time $O(\sqrt n/\log n)$ in the worst case, which is attained whenever $n$ is a semiprime with both factors roughly the same size (say, $p \le q < 2p$). If $n$ is a $b$-bit number, the time taken is $O(\sqrt2^b/b)$ and hence the algorithm takes exponential time.