kyle wenly

Greenhorn

Posts: 2

posted 3 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!

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!

Ulf Dittmer

Rancher

Posts: 42972

73

posted 3 years ago

- 2

Welcome to the Ranch.

It's "n-1" because you need n-1 comparisons, not n comparisons, to find the min or max of n numbers.

But I think you're too focused on details that do not matter for a Big-O or similar analysis. Finding the maximum of an n-long list has O(n) complexity. Whether the precise number of steps is n, n-X or n+Y (where X and Y are constant values) makes no difference for this kind of analysis - it would still be O(n). The approximation is valid for large values of n, where small additive constants make no difference.

It's "n-1" because you need n-1 comparisons, not n comparisons, to find the min or max of n numbers.

But I think you're too focused on details that do not matter for a Big-O or similar analysis. Finding the maximum of an n-long list has O(n) complexity. Whether the precise number of steps is n, n-X or n+Y (where X and Y are constant values) makes no difference for this kind of analysis - it would still be O(n). The approximation is valid for large values of n, where small additive constants make no difference.

kyle wenly

Greenhorn

Posts: 2

posted 3 years ago

Ahh thank you! I forgot that n+1 and n/2 would still be n according to the definition:

"T(N) is O(f(N)) if there are positive constants c and n0 such that T(N) ≤ cf(N) when N ≥ n0. (O(f(N)) are the functions that grow no faster than f(N).)"

Ulf Dittmer wrote:Welcome to the Ranch.

It's "n-1" because you need n-1 comparisons, not n comparisons, to find the min or max of n numbers.

But I think you're too focused on details that do not matter for a Big-O or similar analysis. Finding the maximum of an n-long list has O(n) complexity. Whether the precise number of steps is n, n-X or n+Y (where X and Y are constant values) makes no difference for this kind of analysis - it would still be O(n). The approximation is valid for large values of n, where small additive constants make no difference.

Ahh thank you! I forgot that n+1 and n/2 would still be n according to the definition:

"T(N) is O(f(N)) if there are positive constants c and n0 such that T(N) ≤ cf(N) when N ≥ n0. (O(f(N)) are the functions that grow no faster than f(N).)"