On the Average Complexity of Strong Star Normal Form