Win a copy of Escape Velocity: Better Metrics for Agile Teams this week in the Agile and Other Processes 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:
  • Campbell Ritchie
  • Liutauras Vilda
  • Tim Cooke
  • Paul Clapham
  • Jeanne Boyarsky
Sheriffs:
  • Ron McLeod
  • Frank Carver
  • Junilu Lacar
Saloon Keepers:
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Al Hobbs
  • Carey Brown
Bartenders:
  • Piet Souris
  • Frits Walraven
  • fred rosenberger

Big-O

 
Ranch Hand
Posts: 373
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Is time complexity of a code segment the same as Big-O of it?
 
Saloon Keeper
Posts: 7417
170
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
For the most part, yes. You also use big-O notation for space complexity (memory) or other complexity measures you can think of, but the most common use by far is for time complexity.
 
Saloon Keeper
Posts: 14325
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
They are related but different terms.

"Time complexity" is a rather vague term and can refer to different things. For instance, there is "worst case time complexity", "best case time complexity" and "average case time complexity". Big O can be used to express an upper bound on any of these. If you don't explicitly state what case Big O expresses an upper bound for, people will assume Big O means "upper bound to the worst case time complexity".
'
You can also use Big O to express an upper bound to space complexity for a specific case. You can use Big Omega to express a lower bound on either time or space complexity for a specific case.
 
reply
    Bookmark Topic Watch Topic
  • New Topic