posted 7 years ago
Hi guys, I'm new here. I just wanted some clarifications on how some of this works. Let's say we have this scenario:
Example: given a list of n>=1 entries, output the largest entry in the list.
Basic operation: comparison of two list entries.
Class of algorithms: algorithms that can compare and copy list entries, but do no other operations.
Upper bound: assume that we implement the list l using an array. 0. max = retrieve(first(l),l);
1. index = next(first(l),l);
2. while (index != end_list(l)) {
3. if (max < retrieve(index,l))
4. max = retrieve(index,l)
5. }
where:
first(l) returns the first position in l.
next(x,l) returns the position following position x in list . retrieve(x,l) returns the list entry at position x in list l.
Comparisons are done in line 3, which is executed exactly n-1 times. Thus, t(n)=n-1 is an upper bound on the number of comparisons.
Ok, let's say we have a list named xs of distinct values like [1,2,3,4,5,6]. In a list of n distinct entries, n-1 would not be the absolute max (I'm assuming because we start at position 0 and navigate to position 5 in this case). So the absolute max would be n because a particular entry is not the maximum only if it is smaller than at least one other entry in the list. Each comparison has only one "loser" in the algorithm, so f(n)=n-1 is a lower bound on the number of comparisons needed. Therefore functions f and t are equal and we should stop there right? Ok, the main question I'm asking is the initial n-1. Is it because we already have a starting index (position 0 in this case) and thus we can only execute n-1 times, with n times creating an array/list out of bounds error? But, also n-1 would not be the max...huh? I'm a little confused!
Thanks in advance!