A method of estimating gain of a time-to-digital converter (TDC) includes: capturing a TDC output sample; calculating a gradient in response to the TDC output sample; and adjusting a TDC normalizing gain based on the calculating step. Another method of calibrating gain of a TDC includes: capturing a phase error which is derived from a TDC output sample, a reference phase and a variable phase; calculating a gradient in response to the phase error; and adjusting a TDC normalizing gain based on the calculating step.