After a brief introduction to the concept of Computational Complexity, I will show how to calculate it in several theories with boundaries in two dimensions. In particular, I will consider a free boson discretized on a lattice with Dirichlet boundary conditions, and "Boundary CFTs" with a holographic dual. I will identify certain contributions in the results for the Complexity which are characteristic of the presence of boundaries. Moreover, the results in the two most popular holographic prescriptions, the so-called "CV" and "CA" prescriptions, are qualitatively different. Thus, one can obtain information on the fitness of the holographic prescriptions in describing faithfully the Complexity of the dual states.