-
February 8th, 2012, 06: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 minimum-level BST? Explain.
-
February 8th, 2012, 07: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, 07: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, 07: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, 10: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: 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.
-
February 11th, 2012, 01: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 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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|