Win a copy of Cross-Platform Desktop Applications: Using Node, Electron, and NW.js this week in the JavaScript forum!
programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering Languages Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Big Oh analysis explanation needed

kyle wenly
Greenhorn
Posts: 2
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!

Ulf Dittmer
Rancher
Posts: 42972
73
• 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.

kyle wenly
Greenhorn
Posts: 2
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).)"