For a basic plain vanilla 401(k) that IS NOT a safe-harbor plan, what are the notice requirements for the discretionary matching formula the sponsor uses? Is there any notice required at all? In this case, discretionary matching contributions are going to begin in the middle of the plan year.

Can matching begin mid-year using a formula such as the one that follows: $.50 match for each dollar contributed in the second half of the plan year, limited to 4% of each participant's compensation for the second half of the plan year? The plan document does not mention whether discretionary matching will be based on compensation for any specific time period.

Sure you can. With a discretionary matching program, you can make it whatever you want. But...you have to let employee/participants know what it is. You will get the best effect from a matching contribution if you announce it before the beginning of the "year", because participants will know if they contribute, what they will get. By announcing in the middle of the year, (without knowing the provisions of your plan) you will need to have the ability to enroll participants in the middle of the year. Also, I am not going to go into the possible discrimination issue if only the highly paid employees sign-up in prior to or at the beginning of the year, and the non-highly paid employees can't (or are not allowed to) join after the announcement of the mid-year matching contribution.