Adding column with default value to large table

The major problem is that this needs to write to every single row, which is heavily logged as one single transaction. One way to minimize the impact to the log (and this works best if you don't have silly 10% autogrow settings on your log file) is to break up the work as much as possible:

1. add a NULlable column:

   ALTER TABLE dbo.myTable 
    ADD NewColumnID INT CONSTRAINT DF_Constraint DEFAULT 0;
   

2. Update the rows in a batch, say 10K rows at a time (this will minimize log impact - see this blog post for background):

   BEGIN TRANSACTION;
   SELECT 1;
   WHILE @@ROWCOUNT > 0
   BEGIN
     COMMIT TRANSACTION;
     BEGIN TRANSACTION;
   
     UPDATE TOP (10000) dbo.myTable SET NewColumnID = 0;
   END
   COMMIT TRANSACTION;
   

3. Add a check constraint (see these answers for more detail):

   ALTER TABLE dbo.myTable WITH CHECK
     ADD CONSTRAINT NewCol_Not_Null
     CHECK (NewColumnID IS NOT NULL); 
   

   You can save some time by using NOCHECK here, but as Martin explained in his answer, that is a one-time savings that could cost you plenty of headaches over the longer term.

This was addressed in this previous question, but the accepted answer there uses NOCHECK without any disclaimer about how an untrusted constraint can impact execution plans.

No, as of SQL Server 2012, this will be instantaneous:

Prior to SQL Server 2012 when you add a new non-NULLable column with default values to an existing table a size-of data operation occurs: every row in the table is updated to add the default value of the new column. For small tables this is insignificant, but for large tables this can be so problematic as to completely prohibit the operation. But starting with SQL Server 2012 the operation is, in most cases, instantaneous: only the table metadata is changed, no rows are being updated.

http://rusanu.com/2011/07/13/online-non-null-with-values-column-add-in-sql-server-11/

The time it takes for an update query to run is completely dependent on the underlying hardware and no one here can give you a clear answer. Updating 40 million records could take seconds or days depending on the hardware.. specifically, amount of RAM in the machine and speed of the hard drives.

That said, if a simple update like you shown takes a "VERY LONG TIME" then an alter statement is likely to take as long or longer.