What confidence and error width do you deisre in the sample size?
Company has n=5,000,000 customers that are using service X. We need to determine customer satisfaction with service X through phone survey.
Is there a formal way to determine optimal sample size (assuming that all calls will be answered)?
It's good you have identified the confidence level required. The error width will be how far either side of this you can allow for.
will require more samples than
Have a read of this guy.
PEOD6/PD006: Determining Sample Size
There is a table at the bottom that will give you some numbers to consider.