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.

Sounds like homework. What do you have so far?

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

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

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

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.