Search Index build duration raises disproportionately when element count increases

Reproduction steps:

1. Open the attached project (“SearchIndexManager.zip“)
2. Select Scene “Assets/Scenes/ReproScene”
3. Press Window>Search>Index Manager
4. Press the button “Build”
5. Remove prefab “3072 Cube Container” from the Scene
6. Go to “Assets/Container Packages”
7. Import asset “6144 Cube Container”
8. Add prefab “6144 Cube Container” to Scene
9. Press Window>Search>Index Manager
10. Press the button “Build”
11. Compare building time

Expected result: Search index build duration is linear to its complexity
Actual result: Search index build duration is disproportionate

Reproducible with: 2021.3.11f, 2022.1.18f1, 2022.2.0b9, 2023.1.0a12
Couldn't test with: 2020.3.40f1(Index manager does not exist)

Reproduced on: Windows 11