Help coderanch get a
new server
by contributing to the fundraiser
  • 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
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Timing Complexity

 
Ranch Hand
Posts: 185
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi all,

I am really not able to understand how exactly do we calculate the O(n) of any algorithm. suppose my algorithm has a complexity of 3n/2 + 1 then how would i say what is O(n) of it. Please help me understand that. any pointers would be useful
 
Marshal
Posts: 79532
380
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Try this link, which I hope will give you Niklaus Wirth's algorithms book. As far as I know you can legally download it as a .pdf. There is bound to be a chapter about complexity and about the big-O notation.
 
Ranch Hand
Posts: 92
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Jacob Sonia wrote:
I am really not able to understand how exactly do we calculate the O(n) of any algorithm. suppose my algorithm has a complexity of 3n/2 + 1 then how would i say what is O(n) of it. Please help me understand that. any pointers would be useful



The Ordo system is concerned with the overall complexity. In an expression like 3n/2 + 1 you pick the worst contribution and remove the multiplicative constant. This gives you O(n). This tells you that the complexity is linear. I means that if you double the data input, the execution time will double. Any expression describing a line (is of the form k*n + m) belongs to the same category, that is O(n).
 
You guys wanna see my fabulous new place? Or do you wanna look at this tiny ad?
We need your help - Coderanch server fundraiser
https://coderanch.com/t/782867/Coderanch-server-fundraiser
reply
    Bookmark Topic Watch Topic
  • New Topic