If in doubt, better to air on the high side. You can always buy more CPU cycles -- they're incredibly cheap these days -- but you can't squeeze a single extra cycle out of a too-small one, no matter how deeply you optimize.
And, once you've written most of the thing for one platform, then find you need to port it to something else -- that's wasted time developing for both.
As for estimation, that requires a lot of experience. There's no simple answer here, because you have to know precisely what it is you're doing, and how the platform will handle it. AVR for example, you can count cycles and know precisely how long a function will take to execute -- but this is only after you have the machine code output from the compiler (or hand written assembler!). This is true for most lower-tier MCUs.
Whereas, if it has instruction/data caches ("flash accelerator" etc.), all bets are off -- but some average figures may prove accurate/reliable enough to work with. So, most chips under 60MHz or so are easy enough in this way (counting cycles), and things just get worse as you go to higher performance chips, with caches, pipelines and so on.
For example, say your audio update loop just pulls values from ROM and dumps it to a -- what are you using for DAC anyway? Which, keep that in mind as well: hardware can offload many challenges you'll otherwise have to solve with yet more software; for instance, having an internal buffered DAC would be ideal, unbuffered okay, external SPI poor (will you have to interleave writes with memory reads? can you use two SPI ports independently?). Anyway, if you're doing that and nothing else, I would guess that will be very easy on mega328. Probably wouldn't run with optimization disabled, but GCC should do well enough with it on. Maybe Arduino library stuff is fast enough as well (well... maybe).
But say you wanted to add something seemingly simple, like a volume control -- now you need to receive the value from memory, and multiply by a parameter, and this needs to be done in fixed or floating point -- which if you don't know how to do fixed point, you might opt for the "simpler" floating point method, but this will take hundreds of cycles to complete using built-in (library) function calls -- AVR has no hardware floating point support. And with a maximum 32MHz clock rate*, taking hundreds of cycles leaves hardly any time to get that data in and out. (It might actually manage, if just the one float op; the libraries perform well for what they are. But just a couple ops and you're easily over the limit.)
*Mostly for XMEGA series AVRs, I think. Or if you try overclocking others, which, eh, it's been tried, it can work; if maybe not reliably.
Another point of note: programming languages make no consideration of execution time. C language for example guarantees that valid code will do what it's supposed to**, not how long it'll take to do it on any particular platform. Or that it'll even fit on a platform at all -- you can easily write an interrupt service routine (ISR) that takes all the time in the world, freezing up the system; it's not up to the language to tell you you're doing something "wrong" like that. Or if you write 20k of program code and try to stuff it on a 8k platform; the compiler can do it just fine but good luck loading it.
**For some values of "suppose". You'll probably not be using fully compliant, no-undefined-behavior code on an embedded platform. Undefined behavior like overflow and bit shifting tricks are great tools, but are hard to use in a universal manner. So, code tends to be idiomatic with these sorts of tricks, which -- in addition to differing hardware interfaces -- also makes porting difficult.
So, in summary:
- Know exactly what you want to do. To the finest grained level possible: not just statements, but individual arithmetic operations even.
- Know how to do it. Understand how the compiler will handle those statements, and how long they will take to execute on a given platform.
- Confirm execution time by writing in checks (e.g. set/clear an IO pin at the start/end of the function; mind this won't include pre/postamble code i.e. PUSH and POP, etc.) or inspecting the machine code output (assumes you know the instruction set for the platform!).