Power estimation is an important issue in digital VLSI circuit design. The estimation of average power dissipation of a circuit through exhaustive simulation is impractical due to the large number of primary inputs and their combinations. In this paper, two algorithms based on least square estimation are proposed for determining the average power dissipation in CMOS circuits. Least square estimation converges faster by attempting to minimize the mean square error value during each iteration. Two approaches namely, the sequential least square estimation and the recursive least square estimation, are investigated. The proposed methods are distribution independent in terms of the input samples, unbiased and point estimation based. Experimental results for the MCNC '91 and the ISCAS '89 benchmark circuits are presented. While the sequential least square algorithm performs comparable with the Monte-Carlo method, the recursive least square method converges up to 12 times faster than the Monte-Carlo technique.