Win a copy of Kotlin in Action this week in the Kotlin forum!
programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering Languages Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

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

alex lotel
Ranch Hand
Posts: 191
how do we count the loops thing??

Ulf Dittmer
Rancher
Posts: 42972
73
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
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: 42972
73
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:

 Did you see how Paul cut 87% off of his electric heat bill with 82 watts of micro heaters?