Using Kolmogorov complexity as input "size" Say we have a computational problem, e.g. 3-SAT, that has a set of problem instances (possible inputs) $S$. 
Normally in the analysis of algorithms or computational complexity theory, we have some sets
$$I(n) = \{w \in S : |w| = n\}$$
of all inputs of length $n$, and a function $T(w)$ that gives the running time of some solution algorithm $A$ on input $w$. 
The worst-case running time sequence for $A$ is then
$$ f_n = \max_{w \in I(n)} T(w). $$ 

Let us now define the sets
$$ I^K(n) = \{w \in S : K(w) = n \}$$
of all inputs with Kolmogorov complexity $n$, and let us define the sequence
$$ f^K_n = \frac{1}{\left|I^K(n)\right|} \sum_{w \in I^K(n)} T(w). $$
Here $f^K$ is the average running time sequence for $A$, except where the "size" of inputs is their Kolmogorov complexity, not their length.

Are there algorithms for which $f_n$ is asymptotically significantly different from $f^K_n$?  If so, are there problems whose time complexity changes when using this different way of analyzing algorithms?
Consider the parity function (or any other function that depends on all/most bits of the input). For the parity function, $T(w) = \Theta(|w|)$. So 
$$f_n = \Theta(n).$$
On the other hand, 
$$f_n^K = \Theta\left(\frac{1}{|I^K(n)|} \sum_{w:K(w) = n} |w|\right) \geq \Omega\left(\frac{1}{2^n} \max_{w:K(w) = n} |w|\right).$$

Note that $K(2^{2^n}) = O(n)$. Thus $$\max_{w:K(w) = n} |w| \geq 2^{2^{\Omega(n)}}$$ and $f_n^K \geq 2^{2^{\Omega(n)}} / 2^n \to \infty$. Similarly, $K(2^{\dots^{2^{2^n}}}) = O(n)$; thus $f_n^K \geq 2^{\dots^{2^{2^{\Omega(n)}}}}/2^n$ “grows very rapidly”. Moreover, it's not hard to see that there is no computable upper bound for $f_n^K$.