Algorithm complexity

[navyaakki]

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.

[BioPhysEngr]

Sounds like homework. What do you have so far?

[navyaakki]

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

[navyaakki]

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

[BioPhysEngr]

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)?

[rrodrigoa]

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.