¿Es posible que se produzca un desbordamiento de stack mientras se usa la ordenación rápida en el tiempo de ejecución promedio?

Sé que esto suena estúpido, pero si asumimos que tenemos suerte y obtenemos una complejidad de tiempo promedio de O (NlogN) cada vez que hacemos una clasificación rápida, entonces, independientemente del tamaño de la matriz, nunca tendremos una falla de segmentación porque incluso aunque estamos haciendo innumerables llamadas recursivas y estamos asignando espacio a la stack de llamadas, nunca agotamos toda la memoria reservada de la stack de llamadas porque la estamos desglosando en el tiempo de inicio de sesión y la estamos combinando en tiempo lineal.

Por supuesto, esto es lo que pienso sobre una pregunta para llevar a casa que mi profesor nos dejó para pensar cuando estábamos en fallas de segmentación en nuestra clase. ¿Me equivoco al pensar que una falla de segmentación nunca ocurre si asumimos que siempre tiene una complejidad de tiempo de ejecución promedio?

Aquí está la pregunta:

Si tuviéramos un sistema informático con un montón de 2 GB y el tamaño de la stack de llamadas para una aplicación es de 1 MB. Y suponga que cada llamada recursiva a quicksort requiere que se asignen 256 bytes a la stack de llamadas. ¿Es posible obtener un desbordamiento de stack?

EDITAR:

Esto es asumiendo que nuestro algoritmo se ejecutará en complejidad de tiempo promedio, con las especificaciones de la computadora anotadas en la pregunta. Lo siento por no ser lo suficientemente específico.

EDIT2:

Nuestro tamaño de entrada será igual o inferior a 2 gb, que es nuestro tamaño de stack.

No puede calcular esto sin tener el número de elementos que está considerando para su entrada. El error de desbordamiento de stack en este caso sería una función de “número de elementos” y “tamaño de stack”. Fuera de estos te falta uno.

Los progtwigs que utilizan el enfoque recursivo tienen más probabilidades de llegar a un desbordamiento de stack cuando la entrada es relativamente grande. Por otro lado, el enfoque iterativo es muy eficaz y seguro. Como se indicó anteriormente, la respuesta a su pregunta depende de cuán grande sea su opinión. Pero, para tener una idea de qué tan rápido un progtwig recursivo puede dañar una stack en comparación con un progtwig iterativo, puede mirar este enlace: http://www.codeproject.com/Articles/21194/Iterative-vs-Recursive -Enfoques

Solo como un consejo general, no es una buena idea usar recursivo en secciones críticas de su progtwig.