Win a copy of Head First Android this week in the Android forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Tim Cooke
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • Liutauras Vilda
Sheriffs:
  • Jeanne Boyarsky
  • Rob Spoor
  • Bear Bibeault
Saloon Keepers:
  • Jesse Silverman
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Piet Souris
  • Al Hobbs
  • salvin francis

Big Oh analysis explanation needed

 
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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!
 
Rancher
Posts: 43027
76
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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).)"
 
You showed up just in time for the waffles! And this tiny ad:
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
reply
    Bookmark Topic Watch Topic
  • New Topic