CODEWITHSUNDEEP
time-complexitycomplexity-theoryheapsortspace-complexitycode-complexity
Saurav
Saurav

Reputation: 597

Finding complexity of heap function

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.

Upvotes: 0

Views: 52

Answers (1)

ford prefect
ford prefect

Reputation: 7388

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.

Upvotes: 1

Related Questions