Простой и удобный анализ временной и пространственной сложности для Heapsort

Мне не удалось найти простой и понятный анализ временной или пространственной сложности для Heapsort. Это не повторяющийся вопрос в stackoveflow.

1. Наихудшая временная сложность возьмем только этот пример, для пирамидальной сортировки это O(n log(n)). Как мы можем легко вычислить это?

Сравним с алгоритмом сортировки слиянием.

Сортировка слиянием

void mergeSort(int arr[], int l, int r)    // T(n), n being the number of elements in arr
{ 
    if (l < r) 
    { 
        ........ // constant operations

        mergeSort(arr, l, m);     // T(n/2) since we apply it on aprox half
        mergeSort(arr, m+1, r);   // T(n/2) since we apply it on aprox half

        merge(arr, l, m, r);    // c*n , out of scope to analyse merge() 
    } 
} 

Цель состоит в том, чтобы проанализировать сложность, а не сам алгоритм: https://www.geeksforgeeks.org/merge-sort/

Следовательно, если n — количество элементов массива, а c — константа, мы имеем:

T(n) = c, if n=1
T(n) = 2*T(n/2) + c*n, if n>1
so we can rewrite
T(n) = 2*( 2*T(n/4) + c*n/2 ) +c*n
T(n) = 4*T(n/4) + 2cn
T(n) = 4*( 2T(n/8) + c*n/4 ) + 2cn
T(n) = 8*T(n/8) + 3c
...
T(n) = 2^k * T(n/2^k) + kcn
if we use T(1) that we know => 1 = n/2^k => k = log(n) =>
T(n) = 2^(log(n)) * T(1) + nlog(n)
T(n) = n + nlog(n)
=> nlog(n)

Полное объяснение: https://www.youtube.com/watch?v=0nlPxaC2lTw&list=PL2_aWCzGMAwKedT2KfDMB9YA5DgASZb3U&index=6

Теперь давайте рассмотрим пример пирамидальной сортировки.

Я упоминаю, что уже проверил stackoverflow, но четкого ответа нет: Анализ скорости и память для heapsort или heapsort - сложность реализации

Heapsort

Цель состоит в том, чтобы проанализировать сложность, а не сам алгоритм: https://www.geeksforgeeks.org/heap-sort/

// main function to do heap sort 
void heapSort(int arr[], int n) 
{ 
    // Build heap (rearrange array) 
    for (int i = n / 2 - 1; i >= 0; i--) 
        heapify(arr, n, i);                       // n/2 * TH(n)

    // One by one extract an element from heap 
    for (int i=n-1; i>0; i--) 
    { 
        // Move current root to end 
        swap(arr[0], arr[i]); 

        // call max heapify on the reduced heap 
        heapify(arr, i, 0);              // (n-1) * TH(i)
    } 
} 

T(n) = c, if n=1
TH is the time complexity for heapify()
T(n) = n/2 * TH(n) + (n-1) * TH(i) , where i is decreasing from n-1 to 1

Проблема в том, как рассчитать TH(n) = log(n). Потому что на его основе T(n) = n*log(n)

Поэтому код для heapify, для которого нам нужно вычислить TH(n):

// To heapify a subtree rooted with node i which is 
// an index in arr[]. n is size of heap 
void heapify(int arr[], int n, int i) 
{ 
    int largest = i; // Initialize largest as root 
    int l = 2*i + 1; // left = 2*i + 1 
    int r = 2*i + 2; // right = 2*i + 2 

    // If left child is larger than root 
    if (l < n && arr[l] > arr[largest]) 
        largest = l; 

    // If right child is larger than largest so far 
    if (r < n && arr[r] > arr[largest]) 
        largest = r; 

    // If largest is not root 
    if (largest != i) 
    { 
        swap(arr[i], arr[largest]); 

        // Recursively heapify the affected sub-tree 
        heapify(arr, n, largest);       //  how to express TH in terms of n ?
    } 
}

TH(n) = c, if n=1
worst case when the largest if never root:
TH(n) = c + ? * TH( ? )

как написать рекурсивное выражение?

Существует также логическая дедукция, но давайте избежим этой стратегии:

There are log(n) levels. 
Half of the elements will be on the last layer, not touched by heapify().
So log(n) elements are touched. 
This might be a good strategy, but not simple or friendly enough.

2. Пространственная сложность

Как вычислить O(1) как пространственную сложность, если мы используем кучу из n элементов? Или, возможно, значение O(1) неверно: ссылка https://www.bigocheatsheet.com/.