In particular, in A*, the "to be explored" queue has to be kept sorted. This sorting dominates the compute time.
For example, using the "flood fill" method on an 8-bit processor, depending on the state of the maze, it took less than 3milliseconds (hand optimized assembly) to solve a maze. On a Cortex M4, with decently thought through maze representation, but not optimized beyond that, it takes under 1.5milliseconds. This is in the "don't need to bother" category.
This is a great article to start from: https://dl.acm.org/doi/10.5555/26011.26020
PDF version of this can be found online.
What we have done is extended it to be time based rather than distance based i.e. we take into account the motion parameters - acceleration, maximum speed on the straight and through different turns, distance and use that together to generate a cost table and then use the cost table to generate the fastest path.