The time can be reduced by at least half. A partial order $P$ with a given linear extension allows certain optimizations for transitive reduction that are not available without the extension. These optimizations proceed from the fact that we can immediately produce an upper triangular matrix for the incidence relation -- this is a topological sort. The existence of pairs that will force a given pair $(i,j)$ to be reducible can easily be found by examining only pairs in the upper left of the matrix and on the row $i$ and in column $j$.
Label the elements of the set in the order given by the linear extension 1 to $n$, where $n$ is the cardinality of the set.
From the incidences of the partial order $P$, label the entries $D[i,j]$ of a matrix $D$ with 1 if $i \leq n$ in $P$ and 0 otherwise. Perform the following on the matrix $D$.
for (j = n; j > 2; j--) // columns
for (i=1 ; i <= j ; i++) // rows
if (D[i,j] == 1) then
for (k= i+1 ; k < j ; k++)
if (D[i,k] == 0) then loop
if (D[k,j] == 0) then loop
set D[i,j] = 0 // eliminate the chords in situ
break // the first match ends it for (i,j)
endfor
endif
endfor
endfor
The transitive reduction of $P$ will be the subdigraph corresponding to the remaining elements of $D$. The maximum number of pair comparisons needed to eliminate any incidence $D[i,j]$ is $(j-i-1)$. Thus the maximum number of pair comparisons overall will be $\sum_{k=2}^{n-1} \binom{k}{2}$ .