• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

a question on O(n^2) and O(n)

 
alex lotel
Ranch Hand
Posts: 191
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
how do we count the loops thing??
 
Ulf Dittmer
Rancher
Posts: 42968
73
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That depends on the circumstances. Two nested loops could cause an algorithm to have O(n^2) complexity, but not necessarily so. Do you have an example of what you're wondering about?
 
alex lotel
Ranch Hand
Posts: 191
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
can you shed some light on this
i was tought that if we have 2 loops one
inside the other
that its
O(n^2)

but apparently this is not
true
can youexpalin me more of it??
 
Ulf Dittmer
Rancher
Posts: 42968
73
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That depends on what the code is doing in the loop.

This loop describes an O(N^2) algorithm, because everything at line X is being executed N^2 times:

But the following case describes O(N) because the amount of work being done rises linearly with N:
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic