Big O complexity of recursive algorithm

Question

I have a recursive algorithm for the calculation of the weighted median. I'm trying to figure out what the Big-O time complexity will be but i am kinda stuck. Can someone help me please. Thank you all for the help. Here is the code in JAVA:

public static double WeightedMedian(ArrayList<Double> a1, ArrayList<Double> a2, int p, int r) {
if (r == p) {
    return a1.get(p);
}

if (r-p == 0) {
    if (a2.get(p) == a2.get(r)) {
        return (a1.get(p) + a1.get(r))/2;
    }
    if (a2.get(p) > a2.get(r)) {
        return a1.get(p);
    } else {
        return a1.get(r);}
    }

    long q = partition(a1, p, r);  
    double wl=0,wg=0;
    for (int i=p; i<=q-1; i++) {
        wl += a2.get(i);
    }
    for (int i=(int) (q+1); i<=r; i++) {
        wg += a2.get(i);
    }
    if (wl<0.5 && wg<0.5) { 
        return a1.get((int)q);
    } else {
    if (wl > wg) { 
        double x = a2.get((int)q) + wg;
        a2.set((int) q,x);
        return WeightedMedian(a1,a2, p+1, (int)q);
    } else { 
       double x = a2.get((int)q) + wl;
       a2.set((int) q,x);
       return WeightedMedian(a1, a2, (int)q, r);
    }
}

sorry this is my first time posting here so im not really thta good i tried to format the code better but it kept going in strange places etc. Anyway partition code is as follows:

 public static long partition (ArrayList<Double> arr, int low, int high)
{
    double pivot = arr.get(high);

    int i = low - 1;

    for (int j = low; j <= high- 1; j++)
    {
        if (arr.get(j) <= pivot)
        {
            i++;
            double temp = arr.get(i);
            arr.set(i,arr.get(j));
            arr.set(j,temp);
        }
    }
    double temp1 = arr.get(i + 1);
    arr.set(i + 1, arr.get(high));
    arr.set(high,temp1);

    return i + 1;
}

Mathematical description of weighted median

Please could you format your code to make it more readable? The spacing and indentation does not follow normal conventions, which makes it hard to see the overall structure of it. You should also include the code for the missing partition method. — kaya3
– kaya3, Commented Dec 11, 2019 at 18:03
It would also help to explain the problem your algorithm solves, and the key idea of how your algorithm works in English, since that will make the code easier to understand. — kaya3
– kaya3, Commented Dec 11, 2019 at 18:06
I have a mathematical explanation of what weighted median is which im gonna add as a picture now on the question. I know the code is not properly formatted but its my first time writing a question on stack overflow and when i try to format it something goes wrong and its not showed as code anymore but as text i dont really know. Im sorry — MKK
– MKK, Commented Dec 11, 2019 at 18:20
Looks like O(n), all arraylist gets are O(1) and you have 3 for loops, all O(n) — Joe
– Joe, Commented Dec 11, 2019 at 18:30

Joe · Accepted Answer · 2019-12-11 18:37:39Z

public static double WeightedMedian(ArrayList<Double> a1, ArrayList<Double> a2, int p, int r) {
if (r == p) {
    return a1.get(p); //O(1)
}

if (r-p == 0) {
    if (a2.get(p) == a2.get(r)) { //O(1) + O(1)
        return (a1.get(p) + a1.get(r))/2; //O(1) + O(1)
}
if (a2.get(p) > a2.get(r)) { //O(1) + O(1)
    return a1.get(p); //O(1)
} else {
    return a1.get(r);} //O(1)
}

long q = partition(a1, p, r);  
double wl=0,wg=0;
for (int i=p; i<=q-1; i++) { //O(n)
    wl += a2.get(i); 
}
for (int i=(int) (q+1); i<=r; i++) { //O(n)
    wg += a2.get(i); 
}
if (wl<0.5 && wg<0.5) { 
    return a1.get((int)q); //O(1)
} else {
    if (wl > wg) { 
        double x = a2.get((int)q) + wg; //O(1)
        a2.set((int) q,x); //O(1)
        return WeightedMedian(a1,a2, p+1, (int)q);
    } else { 
       double x = a2.get((int)q) + wl; //O(1)
       a2.set((int) q,x); //O(1)
       return WeightedMedian(a1, a2, (int)q, r);
    }
}

So the above method is O(n), from O(1)...+O(n) = O(n)

public static long partition (ArrayList<Double> arr, int low, int high)  {
double pivot = arr.get(high); //O(1)

int i = low - 1;

for (int j = low; j <= high- 1; j++) //O(n)
{
    if (arr.get(j) <= pivot) //O(1)
    {
        i++;
        double temp = arr.get(i); //O(1)
        arr.set(i,arr.get(j)); //O(1)
        arr.set(j,temp); //O(1)
    }
}
double temp1 = arr.get(i + 1); //O(1)
arr.set(i + 1, arr.get(high)); //O(1)
arr.set(high,temp1); //O(1)

return i + 1;
}

And the above method "partition", also O(n), derived by O(1)... + O(n)

So, O(n), as arraylist is direct access with index's and all get/sets are O(1) and all of your loops are O(n)

Collectives™ on Stack Overflow

Big O complexity of recursive algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related