CODEWITHSUNDEEP
javabig-oquicksort
Hello
Hello

Reputation: 286

Time complexity(Java, Quicksort)

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

Upvotes: 3

Views: 817

Answers (3)

Tarun Maganti
Tarun Maganti

Reputation: 3086

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 no,
such that 0<= f(n) <= cg(n) for all n >= no}

enter image description here

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(n2) or O(nlog n).

Upvotes: 2

TDWebDev
TDWebDev

Reputation: 84

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)).

Upvotes: 0

Hendrik T
Hendrik T

Reputation: 191

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)

Upvotes: 0

Related Questions