Finding complexity of heap function

Question

I am going to use the following code for Heap sort (Link: https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/Heap.java)

Given the following code:

public static void sort(Comparable[] pq) {                     // Complexity: O(NLog N)
    int n = pq.length;                                         // Complexity: O(1)
    for (int k = n/2; k >= 1; k--)                             // Complexity: O(N)
        sink(pq, k, n);                                        // Complexity: O(Log N)
    while (n > 1) {                                            // Complexity: O(N)
        exch(pq, 1, n--);                                      // Complexity: O(1)
        sink(pq, 1, n);                                        // Complexity: O(Log N)
    }
}

private static void sink(Comparable[] pq, int k, int n) {      // Complexity: O(Log N)
    while (2*k <= n) {                                         // Complexity: O(Log N)
        int j = 2*k;                                           // Complexity: O(1)
        if (j < n && less(pq, j, j+1)) j++;                    // Complexity: O(1)
        if (!less(pq, k, j)) break;                            // Complexity: O(1)
        exch(pq, k, j);                                        // Complexity: O(1)
        k = j;                                                 // Complexity: O(1)
    }
}
private static boolean less(Comparable[] pq, int i, int j) {   // Complexity: O(1)
    return pq[i-1].compareTo(pq[j-1]) < 0;                     // Complexity: O(1)
}
private static void exch(Object[] pq, int i, int j) {          // Complexity: O(1)
    Object swap = pq[i-1];                                     // Complexity: O(1)
    pq[i-1] = pq[j-1];                                         // Complexity: O(1)
    pq[j-1] = swap;                                            // Complexity: O(1)
}

I wanted to know if my thinking is correct?? I am a bit of a noob in this domain.

Answer 1

Your logic looks correct. The sort function is N + Nlog(N) which does simplify to Nlog(N). Typically you don't do this sort of analysis line by line but instead you just look for every place in the code that involves iteration but this way works.