Time complexity(Java, Quicksort)

Question

I have a very general question about calculating time complexity(Big O notation). when people say that the worst time complexity for QuickSort is O(n^2) (picking the first element of the array to be the pivot every time, and array is inversely sorted), which operation do they account for to get O(n^2)? Do people count the comparisons made by the if/else statements? Or do they only count the total number of swaps it makes? Generally how do you know which "steps" to count to calculate Big O notation.

I know this is a very basic question but I've read almost all the articles on google but still haven't figured it out

so in general, you count all the operations? Like even the for loop increment, if/else and everything? Just curious because for linear search, i was taught that i should only count the number of comparisons because it's the major operation that we're interested in. — Hello
– Hello, Commented Nov 13, 2016 at 2:42
As already mentioned, you count both (all operations). Then those complexities (operation count) will be in addition to each other and you pick the max of them. :) — YoungHobbit
– YoungHobbit, Commented Nov 13, 2016 at 2:47

Tarun Maganti · Accepted Answer · 2016-11-13 04:25:40Z

Worst cases of Quick Sort
Worst case of Quick Sort is when array is inversely sorted, sorted normally and all elements are equal.

Understand Big-Oh
Having said that, let us first understand what Big-Oh of something means.

When we have only and asymptotic upper bound, we use O-notation. For a given function g(n), we denote by O(g(n)) the set of functions, O(g(n)) = { f(n) : there exist positive c and n_o,
such that 0<= f(n) <= cg(n) for all n >= n_o}

How do we calculate Big-Oh?
Big-Oh basically means how program's complexity increases with the input size.

Here is the code:

import java.util.*;
class QuickSort
{
    static int partition(int A[],int p,int r)
    {
        int x = A[r];
        int i=p-1;
        for(int j=p;j<=r-1;j++)
        {
            if(A[j]<=x)
            {
                i++;
                int t = A[i];
                A[i] = A[j];
                A[j] = t;
            }
        }

        int temp = A[i+1];
        A[i+1] = A[r];
        A[r] = temp;
        return i+1;
    }
    static void quickSort(int A[],int p,int r)
    {
        if(p<r)
        {
            int q = partition(A,p,r);
            quickSort(A,p,q-1);
            quickSort(A,q+1,r);
        }
    }
    public static void main(String[] args) {
        int A[] = {5,9,2,7,6,3,8,4,1,0};
        quickSort(A,0,9);
        Arrays.stream(A).forEach(System.out::println);
    }
}

Take into consideration the following statements:

Block 1:

int x = A[r];
int i=p-1;

Block 2:

if(A[j]<=x)
{
     i++;
     int t = A[i];
     A[i] = A[j];
     A[j] = t;
}

Block 3:

int temp = A[i+1];
A[i+1] = A[r];
A[r] = temp;
return i+1;

Block 4:

if(p<r)
{
    int q = partition(A,p,r);
    quickSort(A,p,q-1);
    quickSort(A,q+1,r);
}

Assuming each statements take a constant time c. Let's calculate how many times each block is calculated.

The first block is executed 2c times. The second block is executed 5c times. The thirst block is executed 4c times.

We write this as O(1) which implies the number of times statement is executed same number of times even when size of input varies. all 2c, 5c and 4c all are O(1).

But, when we add the loop over second block

for(int j=p;j<=r-1;j++)
{
    if(A[j]<=x)
    {
        i++;
        int t = A[i];
        A[i] = A[j];
        A[j] = t;
    }
 }

It runs for n times (assuming r-p is equal to n, size of the input) i.e., nO(1) times i.e., O(n). But this doesn't run n times everytime. Hence, we have the average case O(log n) i.e, at least log(n) elements are traversed.

We now established that the partition runs O(n) or O(log n). The last block, which is quickSort method, definetly runs in O(n). We can think of it as an enclosing for loop which runs n times. Hence the entire complexity is either O(n²) or O(nlog n).

How did you make the leap from O(n) to O(n^2) ? I get that for loop takes O(n) time but how can you say it takes O(n^2) just from that?
The last block is runs O(n) times. We can think of it as the for loop enclosing the partition function which itself runs in O(n) time. Hence, O(n) times O(n) which is O(n^2)

Hendrik T · Accepted Answer · 2016-11-13 03:32:57Z

0

It is counted mainly on the size (n) that can grow, so for quicksort an array it is the size of the array. How many times do you need to access each elements of the array? if you only need to access each element once then it is a O(n) and so on..

Temp variables / local variables that is growing as the n grows will be counted. Other variables that is not growing significantly when n grows can be count as constant: O(n) + c = O(n)

edited Nov 13, 2016 at 3:32

answered Nov 13, 2016 at 3:27

Hendrik T

1917 bronze badges

Comments

TDWebDev · Accepted Answer · 2016-11-13 03:43:57Z

Just to add to what others have said, I agree with those who said you count everything, but if I recall correctly from my algorithm classes in college, the swapping overhead is usually minimal compared with the comparison times and in some cases is 0 (if the list in question is already sorted).

For example. the formula for a linear search is

T= K * N / 2.

where T is the total time; K is some constant defining the total computation time; and N is the number of elements in the list.

ON average, the number of comparisons is N/2.

BUT we can rewrite this to the following:

T = (K/2) * N

or redefining K,

T = K * N.

This makes it clear that the time is directly proportional to the size of N, which is what we really care about. As N increases significantly, it becomes the only thing that really matters.

A binary search on the other hand, grows logarithmically (O log(N)).

Collectives™ on Stack Overflow

Time complexity(Java, Quicksort)

3 Answers 3

5 Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

Comments

Comments

Related