1
$\begingroup$

I've been given a question that states I will be given a set of itineraries, which are basically tuples in the form (cost, time) for airplane flights. An itinerary dominates another itinerary if its cost and time are less than the second itinerary's. If there exists an itinerary that dominates the current itinerary, then the current itinerary is considered undesirable. Otherwise, it is desirable. The algorithm gets a set of itineraries S and must output all desirable itineraries using divide-and-conquer. I need to calculate the time complexity/solve the recurrence relation.

Here is some pseudo-code of the algorithm:

Itinerary[] removeUndesirables(Itinerary[] initArr, int start, int end)
{
    Itinerary[] arr = initArr;

    // If 4 or more itineraries in set…
    if (arr.length > 3)
    {
        int middle = (start + end) / 2;

        // Recursively split and remove undesirable itineraries.
        Itinerary[] leftHalf  = removeUndesirables(arr, 0, middle);
        Itinerary[] rightHalf = removeUndesirables(arr, middle + 1, end);

        // Combine the two halves. Combining takes worse-case O(n)
        arr = combine(leftHalf, rightHalf);
    }

    // For each itinerary in range arr[0] -> arr[n – 1]…
    for (int i = 0; i < arr.length; i++)
    {
        // For every itinerary after the current in range arr[1] -> arr[n]…
        for (int j = 0; j < arr.length; j++)
        {
            // Compare arr[i] and arr[j], skip if i == j. Remove 
            // arr[i] if found undesirable.
        }
    }

    // Return the combined set that has been purged of undesirables.
    return arr_2;
}

// Get desirable itineraries by remove all undesirable ones.
Itinerary[] searchForDesirableItineraries(Itinerary[] arr)
{
    return removeUndesirables(arr, 0, arr.length);
}

I am stuck on the recurrence relation, however.

  • Comparing all itineraries in the set for undesirableness takes O(n^2) time.

  • Search left half of size n/2 for undesirables. This takes worse-case T($(n/2)^2$).

  • Search right half of size n/2 for undesirables. This takes worse-case T($(n/2)^2$).

  • Combining the two half-sets takes, worst-case, O(n) time (where n is the number of elements originally).

$T(n) = 2T((n/2)^2) + O(n^2) + O(n)$

$T(n) = 2[2T((n/4)^2) + {n^2}/4] + n^2 + n = 4T((n/2)^2) + {3n^2}/2 + n$

$T(n) = 4[2T((n/8)^2) + {n^2}/16] + {3n^2}/2 + n = 8T((n/8)^2) + {7n^2}/4 + n$

$...$

$T(n) = 2^kT((n/{2^k})^2) + {2^k - 1}/{2^{k-1}}n^2 + n$

Setting $(n/{2^k})^2 = 1$ and solving gives $k = log(n)$, where $log()$ is base 2.

If I plug $k = log(n)$ into the original recurrence equation, I get $2^{log(n)}T(1) + {(2^{log(n)} - 1)}/{(2^{log(n) - 1})} n^2 + n$, which I simplify to $2^{log(n)}T(1) + 2n^2 - n$.

$2n^2-n$ doesn't make sense to me. I expected my algorithm to be $n^2log(n)$. Why is my recurrence relation wrong?

$\endgroup$
4
  • 1
    $\begingroup$ Welcome to CS.SE! Can you clarify which question you want answered? It sounds like your primary question is "what is wrong with my solution to the recurrence relation" -- is that right? If so, I suggest removing all the material at the top about the problem statement, your code, your algorithm, etc., and just ask about your particular approach to solving that recurrence relation. If you also want to know whether there is a better way to solve the original problem, you can ask that separately -- this site's format works best when you ask only one, narrowly focused question per post. $\endgroup$
    – D.W.
    Commented Feb 28, 2017 at 21:20
  • $\begingroup$ Would just asking how to solve the question using divide-and-conquer be acceptable? I know stack exchange generally doesn't like getting homework problems without the person showing their work, hence why I included all the steps I took to get to the recurrence relation. $\endgroup$
    – Qwurticus
    Commented Feb 28, 2017 at 22:50
  • $\begingroup$ Well, like I said, you seem to have two separate questions: (a) how do I solve this problem with divide-and-conquer?, (b) is my solution to this recurrence relation correct? I suggest that you post them separately: i.e., edit this post to ask about only one of them, and post the other separately. Yes, we want you to try to solve it on your own first and ask a specific question about the problem or about where you got stuck. Showing effort towards (b) doesn't really address that for (a). $\endgroup$
    – D.W.
    Commented Mar 1, 2017 at 1:31
  • $\begingroup$ For (a), it sounds like you already have an answer, so it's not entirely clear to me what more you want. Also, this site is for algorithms, not code, so we'd ask you to replace your code with concise pseudocode that is understandable even by people who don't know C/Java. For (a), your attempt at solving the recurrence relation doesn't really seem relevant to the question. For (b), I've given some advice on how to formulate that question. Those are just my personal thoughts and attempt to get you the best help, within this site's format and mission. Others might have a different perspective. $\endgroup$
    – D.W.
    Commented Mar 1, 2017 at 1:32

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.