• Post Reply Bookmark Topic Watch Topic
  • New Topic

Timing Complexity  RSS feed

 
Jacob Sonia
Ranch Hand
Posts: 183
  • Mark post as helpful
  • send pies
  • 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
 
Campbell Ritchie
Marshal
Posts: 56529
172
  • Mark post as helpful
  • send pies
  • 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.
 
Ulrika Tingle
Ranch Hand
Posts: 92
  • Mark post as helpful
  • send pies
  • 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).
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!