Bem, primeiro você escreve matematicamente o que quer, "para que valores de
[tex3]n[/tex3] a ordenação por inserção supera a ordenação por intercalação?" A ordenação por inserção é executada em
[tex3]8n^2[/tex3] etapas, enquanto a ordenação por intercalação é executada em
[tex3]64n \log_{10} n[/tex3] etapas. Então, queremos descobrir quando:
[tex3]8n^2>64n \log_{10} n[/tex3]
[tex3]n^2>8n \log_{10} n[/tex3]
[tex3]n>8\log_{10}n[/tex3], já que
[tex3]n\neq0[/tex3]
Já que
[tex3]n[/tex3] é o número de etapas, então
[tex3]n\in \mathbb{N}[/tex3]. Assim, podemos dividir em casos baseados no número de dígitos de
[tex3]n[/tex3].
- Se [tex3]1\leq n \lt 10[/tex3]
[tex3]0\leq \log_{10}n\ <1[/tex3]
[tex3]0\leq 8\log_{10}n\ <8[/tex3]
Como
[tex3]8 >8\log_{10}n[/tex3], então se
[tex3]n=\{8,9\}[/tex3],
[tex3]n >8\log_{10}n [/tex3].
- Se [tex3]10\leq n <100[/tex3]
[tex3]1\leq \log_{10}n\ <2[/tex3]
[tex3]8\leq 8\log_{10}n\ <16[/tex3]
Como
[tex3]n=100\implies8\log_{10}n\ =16[/tex3], podemos ver que
[tex3]n[/tex3] sempre será maior que
[tex3]8\log_{10}n[/tex3]. Assim, daqui pra frente,
[tex3]n[/tex3] sempre terá ordem de grandeza maior que
[tex3]8\log_{10}n[/tex3].
Assim, só nos resta testar os valores entre 1 e 7.
- [tex3]n=1\implies 8\log_{10}n=0[/tex3], então [tex3]n>8\log_{10}n[/tex3]
- [tex3]n=2\implies 8\log_{10}n\approx 2,4[/tex3], então [tex3]n<8\log_{10}n[/tex3]
- [tex3]n=3\implies 8\log_{10}n\approx 3,8[/tex3], então [tex3]n<8\log_{10}n[/tex3]
- [tex3]n=4\implies 8\log_{10}n\approx 4,8[/tex3], então [tex3]n<8\log_{10}n[/tex3]
- [tex3]n=5\implies 8\log_{10}n\approx 5,5[/tex3], então [tex3]n<8\log_{10}n[/tex3]
- [tex3]n=6\implies 8\log_{10}n\approx 6,2[/tex3], então [tex3]n<8\log_{10}n[/tex3]
- [tex3]n=7\implies 8\log_{10}n\approx 6,7[/tex3], então [tex3]n>8\log_{10}n[/tex3]
Assim, concluímos que para
[tex3]\{n\in \mathbb{N}/n=1 \text{ ou } n\geq 7\}[/tex3], a ordenação por inserção supera a ordenação por intercalação.