Self-efficacy represents a person's belief that he or she can perform a particular task. It has been found to correlate with academic achievement and people's choice of subjects and career. While relatively widely studied, self-efficacy has not received much attention in tertiary physics. Therefore, we adapted and validated a short Physics Self-Efficacy Questionnaire before administering it four times in one year to the first-year physics cohort at the University of Sydney (N between 122 and 281). Investigating whether gender and prior formal physics instruction mattered to students' physics self-efficacy, we found that both showed a significant effect. Females consistently reported lower self-efficacy than males, and males with no prior formal physics instruction showed the highest self-efficacy of any subgroup, suggesting a 'male overconfidence syndrome'. Investigating correlations between students' physics self-efficacy and end-of-semester physics examination scores, these only seemed to develop after a relatively long time of physics study (of the order of a year or more); females developed such a correlation faster than males. We conclude that gender and prior formal instruction in physics do matter when studying physics self-efficacy, which may have important consequences both for the study of self-efficacy itself, and for the way tertiary physics is taught.