John Fredsted suggested using the following procedure (slightly modified) to determine whether an expression was deeply algebraic.

isDeeplyAlgebraic := proc(x)
	if not type(x,'algebraic') then false
	elif type(x,'atomic') then true
	else andmap(procname,x)
	end if
end proc:

TypeTools:-AddType('DeeplyAlgebraic1'
                   , proc(x)
                         if not x :: 'algebraic' then false;
                         elif x :: 'atomic' then true;
                         else andmap(type,x,'DeeplyAlgebraic1');
                         end if;
                     end proc);

The first is a completely flat expression, the second is deeply nested.  The following graphs plot the time required to determine whether each expression is "deeply algebraic" as n increases, with each approach. The graph on the left is the time required to evaluate expr1, the graph on right is for expr2.  The red plot corresponds to the procedure, the green plot corresponds to the type. As you can see, for both flat and nested expressions, the procedure is significantly faster than the type.

I then did some testing to see whether the type matching could be improved.  A more efficient use of the type mechanism is to use a structured type rather than a procedure.  Alas, I don't believe that it is possible to create a purely structured type, with no use of 'satisfies', that is equivalent to what we want.  Here is the best I could come up

TypeTools:-AddType('DeeplyAlgebraic3'
                   , 'And'('algebraic'
                           , 'Or'('atomic'
                                  , 'satisfies'(x->andmap(type,x,'DeeplyAlgebraic3'))
                                 )));

Adding that to each graph gives the following two plots

The yellow line (p3) corresponds to this new type.  For expr1, the flat expression, it is significantly faster than the previous type, and approaches the speed of the standalone procedure.  Alas, for expr2, the nested expression, it is even slower than the previous type.  However, the reason it is slower is that with a nested expression the 'satisfies' part of the type has to be evaluated, which generates a call to a user-level procedure.

This observation suggests that if the type could be expressed as a structured type, with no use of 'satisfies', it might be significantly more efficient.  While I can see no way to do that with the desired predicate, it is possible to construct a type specific to these two examples:

TypeTools:-AddType('nestedF', 'And(algebraic,Or(atomic,function(Or(atomic,nestedF))))');

This isn't equivalent to the original predicate because it only works with functions, not operators (+, *, etc).

Here are the results with that type

Now we are making progress.  The blue plot (p4) is the time for this restricted type.  It is significantly faster than even the standalone procedure.

Note that if there were a structured type, say allops, that returned true if all of the operands of an expression match the given type, then we would be able to construct a purely structured type that matches our original predicate, that is,

TypeTools:-AddType('DeeplyAlgebraic4'
                   , 'And(algebraic
                          , Or(atomic
                               , allops(DeeplyAlgebraic4)))');