As mentioned in my comment, there are two possible problems. One is that you are puzzled why only some of the labels are changed in size. Matplotlib differentiates between major and minor ticks, and your approach only modifies the major y-ticks. This is easily resolved by accessing the axis object with ax.tick_params():
import matplotlib.pyplot as plt
def make_histogram(listOfAllComplexities):
plt.hist(listOfAllComplexities,ec='black',color='orange',log=True, density=True,bins=5)
plt.xlabel(r'$\tilde{K}(x)$')
plt.ylabel('Frequency',labelpad=20)
ax = plt.gca()
ax.tick_params(axis="both", which="both", labelsize=8)
plt.title('Hist_{0}chars_{1}_{2}'.format(" A ", " B ", " C "))
plt.show()
make_histogram([7.0, 8.1, 7.0, 7.0, 9.3, 7.0, 8.1, 9.3, 7.0, 7.0, 7.0, 5.8, 7.0, 8.1, 9.3, 7.0, 8.1, 7.0, 5.8, 9.3, 5.8, 7.0, 7.0, 8.1, 8.1, 7.0, 8.1, 2.3, 7.0, 5.8, 8.1, 2.3])
Sample output:

As for the formatting of the 10^-1, I assume this is a conscious decision by the matplotlib team, so one can clearly see the decades of the major ticks. However, we can build our own FuncFormatter to imitate the style used for the minor ticks:
import matplotlib.pyplot as plt
import matplotlib.ticker as tkr
import math
def numfmt(x, pos):
sign_string = ""
if x<0:
sign_string = "-"
x = math.fabs(x)
if x == 0:
return r'$\mathdefault{0}$'
base = 10
exponent = math.floor(math.log10(x))
coeff = round(x / (base ** exponent))
return r'$\mathdefault{%s%g\times%s^{%d}}$' % (sign_string, coeff, base, exponent)
myfmt = tkr.FuncFormatter(numfmt)
def make_histogram(listOfAllComplexities):
plt.hist(listOfAllComplexities,ec='black',color='orange',log=True, density=True,bins=5)
plt.xlabel(r'$\tilde{K}(x)$')
plt.ylabel('Frequency',labelpad=20)
ax = plt.gca()
ax.tick_params(axis="both", which="both", labelsize=8)
ax.yaxis.set_major_formatter(myfmt)
plt.title('Hist_{0}chars_{1}_{2}'.format(" A ", " B ", " C "))
plt.show()
make_histogram([7.0, 8.1, 7.0, 7.0, 9.3, 7.0, 8.1, 9.3, 7.0, 7.0, 7.0, 5.8, 7.0, 8.1, 9.3, 7.0, 8.1, 7.0, 5.8, 9.3, 5.8, 7.0, 7.0, 8.1, 8.1, 7.0, 8.1, 2.3, 7.0, 5.8, 8.1, 2.3])
Sample output:

The FuncFormatter function numfmt() is over the top because I only retrospectively noticed that we do not need it for the minor ticks (let matplotlib take care of them) and your histogram frequencies will always be positive. Oh well.