CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 6 of 6
  1. #1
    Join Date
    Feb 2012
    Posts
    5

    Algorithm complexity

    a) The first time you run algorithm A on a dataset of n elements; it is faster than
    algorithm B. The second time you run algorithm A on a dataset of n elements; it is slower than
    algorithm B. Explain how this is possible. Give an example for algorithm A and algorithm B.

    b) If both have n nodes and are sorted smallest to largest, will it be faster to find
    the largest value in a sorted linked list or a minimum-level BST? Explain.

  2. #2
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,016

    Re: Algorithm complexity

    Sounds like homework. What do you have so far?
    Best Regards,

    BioPhysEngr
    http://blog.biophysengr.net
    --
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  3. #3
    Join Date
    Feb 2012
    Posts
    5

    Re: Algorithm complexity

    I got nothing!, I didn't really understand the question, Could you please explain it?
    Thanks

  4. #4
    Join Date
    Feb 2012
    Posts
    5

    Re: Algorithm complexity

    Maybe algorithm A and algorithm B are of different orders?
    for example: one is O(n) and the other is O(n^2).

  5. #5
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,016

    Re: Algorithm complexity

    For (a) this hint may help:
    There are several ways to characterize algorithm complexity. In particular, three parameters are important: best-case, worst-case and average-case complexity. The actual complexity of the algorithm may depend on the input. For example, any sorting algorithm quicksort has average-case complexity of O(n log n), but has a worst-case time complexity for O(n^2). By contrast, insertion sort has best-case complexity of O(n) and worst-case complexity of O(n^2).

    If both of these algorithms are applied to two datasets, D1 and D2, perhaps:

    D1 completes in O(n log n) under quicksort and O(n^2) under insertion sort
    D2 completes in O(n log n) under quicksort, but O(n) [best case!] under insertion sort

    Wouldn't this satisfy the criterion?

    Can you think up another example?

    For (b) I'll ask you a question:

    If you had a sorted linked list, how would you find the largest value?
    If you had a minimal BST, how would you find the largest value?

    For each answer, how many operations does that require (in terms of the size of the list)?
    Best Regards,

    BioPhysEngr
    http://blog.biophysengr.net
    --
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  6. #6
    Join Date
    Feb 2012
    Posts
    2

    Re: Algorithm complexity

    If database is ordered from low to high and you have A as bubble sort (that sorts low to high), it will take time of O(n) to "sort" n elements on the database. B could be a heapsort that always take O(nlogn) and sort database high to low.
    Once you run A gain it will take O(nˆ2) and B will take O(nlogn).

    For the second question, to find the largest value on a linked list you have to go element by element following the pointer so that is O(n), but to find the largest element in a BST you walk from the root to the far most right-down element which will take you O(log2(n)) as the tree has only O(log2(n)) levels.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured