Win a copy of Murach's Python Programming this week in the Jython/Python forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Big Oh analysis explanation needed  RSS feed

 
kyle wenly
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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!
 
Ulf Dittmer
Rancher
Posts: 42970
73
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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).)"
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!