BASH, 133 bytes

File x.bash (no trailing newline):

a=2
while((l<$1));do if((b[a]))
then((c=b[a]));else((c=a,l++));echo $a;fi;((d=a+c))
while((b[d]));do((d+=c));done
((b[d]=c,a++));done

Run:

$ bash x.bash 5
2
3
5
7
11
$ bash x.bash 1000 | wc -l
1000

Primes get calculated by letting known primes jump on the "tape of positive integers". Basically it is a serialised Sieve Of Eratosthenes.

from time import time as t

L = {}
n = 2
l = 0

t0=t()

while l<1000000:

        if n in L:
                P = L[n]
        else:
                P = n
                l += 1
                print t()-t0

        m = n+P
        while m in L:
                m += P
        L[m] = P

        n += 1

...is the same alrorithm in Python and prints out the time when the l-th prime was found instead of the prime itself.

The output plottet with gnuplot by...

plot "fsoe3-timing.dat"

...yields the following:

The gaps probably have something to do with file i/o delays due to writing buffered data to disk...

Using much larger numbers of primes to find, will bring additional system dependent delays into the game, e.g. the array representing the "tape of positive integers" increases continuously and sooner or later will make every computer cry for more RAM (or later swap).

...so getting an idea of the complexity by looking at the experimental data does not really help a lot... :-(