This week's book giveaway is in the Servlets forum.
We're giving away four copies of Murach's Java Servlets and JSP and have Joel Murach on-line!
See this thread for details.
The moose likes Java in General and the fly likes a question on O(n^2) and O(n) Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "a question on O(n^2) and O(n)" Watch "a question on O(n^2) and O(n)" New topic
Author

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

alex lotel
Ranch Hand

Joined: Feb 01, 2008
Posts: 191
how do we count the loops thing??
Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 41060
    
  43
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?


Ping & DNS - my free Android networking tools app
alex lotel
Ranch Hand

Joined: Feb 01, 2008
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
Marshal

Joined: Mar 22, 2005
Posts: 41060
    
  43
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:
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: a question on O(n^2) and O(n)
 
Similar Threads
Big O Notation
Comparison of ArrayList and HashMap
Remove duplicates from char array with O(n) complexity
pagination problem
Sorting method