Leslie Cooper, I agree with your comment on New Holland and here just add a few details. Melchissedec Thevenot published a map in 1663 (post Tasman by about 20 years) clearly indicating the western portion of Terre Australe (the French spelling), approximately where todays Queensland/Northern Territory border stands and continuing to the southern coast, as Hollandia Nova (New Holland) and the eastern portion (including the Gulf of Carpentaria) as Terre Australe. In 1677 Pierre Duval published his 'Carte des Indes Orientales' indicating Novvelle Holande partie de La terre Australe. It is interesting to note that Willem Janszoon named the eastern portion, when he landed near where Weipa stands today, New Zealand. The name did not stick, however, and was used as the name of Tasman's later discovery to the east (which he thought was Staaten Island, South America).
Terra Australis remained the cartographers’ choice of name for the eastern 'half' of the continent until Cook named it New South Wales.
At the time of Cook (1770), the Maories knew the continent as Ulimaroa.