Why elapsed time is an exponential function of the number of elements in a vector that is sorted (MATLAB)

Question

In the following script (that performs "bubble sort" on an row vector) it seems that the time elapsed when matlab executes the sorting depends exponentially on the number of elements in the vector. Why?

tic;
t=zeros(1,50);
for n=1:50
X=randi(10000,[1 n*200]);
a=length(X);
for j=1:1:a-1
    for i=1:1:a-1
        if X(i)>X(i+1)
            temp=X(i);
            X(i)=X(i+1);
            X(i+1)=temp;
        end
    end
end
t(n)=toc;
end
plot(t)

Answer 1

Bubble sort requires $a^2$ comparisons (using your nomenclature). You're also including the random number creation in your time computations, so you're also counting the time it takes to generate a random vector, which you should not be including.

Here's some MATLAB code that uses sort and pre-generates the random numbers. You can replace sort with your own sorting algorithm to evaluate performance.

N = 50;
t = zeros(N,1);
X = rand(N*200,N);

for i=1:N
    x = X(1:200*i,i);
    tic
    S = sort(x);
    t(i) = toc;
end

plot(1:N,t);

---

Edit: Here's code using your bubble sort, and fitting a quadratic polynomial to the time-elapsed data:

N = 50;
t = zeros(N,1);
X = rand(N*200,N);

for i=1:N
    x = X(1:200*i,i);
    tic
    for k=1:length(x)-1
        for l=1:length(x)-1
            if (x(l) > x(l+1))
                temp = x(l+1);
                x(l+1) = x(l);
                x(l) = temp;
            end
        end
    end
    t(i) = toc;
end

plot(1:N,t);
A = t(end)/N^2;
hold on;
plot(1:N,A*(1:N).^2,'r')

And here's a plot. $At^2$ is shown in red. See how well it matches up? This coincides with the $N^2$ number of runs through the list.