
February 8th, 2012, 05:51 PM
#1
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 minimumlevel BST? Explain.

February 8th, 2012, 06:13 PM
#2
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.

February 8th, 2012, 06:17 PM
#3
Re: Algorithm complexity
I got nothing!, I didn't really understand the question, Could you please explain it?
Thanks

February 8th, 2012, 06:18 PM
#4
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).

February 8th, 2012, 09:14 PM
#5
Re: Algorithm complexity
For (a) this hint may help:
There are several ways to characterize algorithm complexity. In particular, three parameters are important: bestcase, worstcase and averagecase complexity. The actual complexity of the algorithm may depend on the input. For example, any sorting algorithm quicksort has averagecase complexity of O(n log n), but has a worstcase time complexity for O(n^2). By contrast, insertion sort has bestcase complexity of O(n) and worstcase 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.

February 11th, 2012, 12:45 PM
#6
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 rightdown 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

Forum Rules

Click Here to Expand Forum to Full Width
