The complexity in this instance is discussing the smoothness of the boundary between the different classes. One way of understanding this smoothness complexity is by asking how likely you are to be classified differently if you were to move slightly. If that likelihood is high then you have a complex decision boundary.
For the $k$-NN algorithm the decision boundary is based on the chosen value for $k$, as that is how we will determine the class of a novel instance. As you decrease the value of $k$ you will end up making more granulated decisions thus the boundary between different classes will become more complex.
You should note that this decision boundary is also highly dependent of the distribution of your classes.
Let's see how the decision boundaries change when changing the value of $k$ below. We can see that nice boundaries are achieved for $k=20$ whereas $k=1$ has blue and red pockets in the other region, this is said to be more highly complex of a decision boundary than one which is smooth.
First let's make some artificial data with 100 instances and 3 classes.
from sklearn.datasets.samples_generator import make_blobs
X, y = make_blobs(n_samples=100, centers=3, n_features=2, cluster_std=5)
Let's plot this data to see what we are up against
Now let's see how the boundary looks like for different values of $k$. I'll post the code I used for this below for your reference.
$k$ = 1
$k$ = 5
$k$ = 10
$k$ = 20
The code used for these experiments is as follows taken from here
from sklearn import neighbors
k = 1
clf = neighbors.KNeighborsClassifier(20)
from matplotlib.colors import ListedColormap
import matplotlib.pyplot as plt
cmap_light = ListedColormap(['#FFAAAA', '#AAFFAA', '#AAAAFF'])
cmap_bold = ListedColormap(['#FF0000', '#00FF00', '#0000FF'])
# Plot the decision boundary. For that, we will assign a color to each
# point in the mesh [x_min, x_max]x[y_min, y_max].
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
np.arange(y_min, y_max, h))
Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
# Put the result into a color plot
Z = Z.reshape(xx.shape)
plt.pcolormesh(xx, yy, Z, cmap=cmap_light)
# Plot also the training points
plt.scatter(X[:, 0], X[:, 1], c=y, cmap=cmap_bold)