Win a copy of Head First Android this week in the Android forum!
  • 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
  • Paul Clapham
  • Ron McLeod
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Rob Spoor
  • Devaka Cooray
  • Jeanne Boyarsky
Saloon Keepers:
  • Jesse Silverman
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
  • Tim Holloway
Bartenders:
  • Jj Roberts
  • Al Hobbs
  • Piet Souris

nested loops

 
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
hey everyone!
can anyone please tell me how to combine two nested loops in one loop so that i can reduce my time complexity....is there any generalized way to do this??
PS - i have wasted my 4-5 hrs in trying to figure it out.
 
Saloon Keeper
Posts: 8738
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
It's hard to say without seeing the loops you have created. Could you please post your code, and UseCodeTags (<--link).
 
Aditya Agrawal
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


This is the code i am talking about.
 
Rancher
Posts: 990
23
Netbeans IDE Oracle MySQL Database Tomcat Server C++ Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Your "time complexity" or your O(n) is still going to be the same, looping is looping no matter how you do it, but what you can do is set things up to break out of the loop when your target become true, that way you are not in the looping structure any longer than needed.  As you seem to have already done.

Aditya Agrawal wrote:hey everyone!
can anyone please tell me how to combine two nested loops in one loop so that i can reduce my time complexity....is there any generalized way to do this??
PS - i have wasted my 4-5 hrs in trying to figure it out.

 
Aditya Agrawal
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
thanks!

 
Carey Brown
Saloon Keeper
Posts: 8738
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
 
Bartender
Posts: 4676
183
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You can optimize things a little at the cost of some coding complexity.

First: you can sort the array, and, given an element e, use a BinarySearch to find the index of K-e.
There are two things to take care of. The index of K-e might be -1, meaning it is not present. And if e is exactly K/2, then we must demand that the indices of e and K-e are different.

A second way is to form a Map<array element, List<indices of that element>>. Now, given an element e, see if the map contains a key K-e. The indices are then map.get(e).get(0) and map.get(K-e).get(0). Here too, we have the slight complexity of having an element that is exactly K / 2 and appearing only once. But that is easy to solve.
 
Piet Souris
Bartender
Posts: 4676
183
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Piet Souris wrote:(...)
The index of K-e might be -1, meaning it is not present.



I meant:
The index of K-e might be negative, meaning it is not present. Excuses!
 
Bartender
Posts: 242
27
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Also if you want to go the route of Binary Searching: you can use either Collections.binarySearch or Arrays.binarySearch to use a Java-implemented Binary Search algorithm (or code your own for learning purposes only). You can also use Java's implementation of a sorting algorithm to sort an array.

An alternative to sorting: if you control when elements are being added to this array, you can add them in a way to ensure that it is sorted. To do this, on your "add" method, you call the Binary Search algorithm on the array, and if it returns a negative number then you can add it at (-index + 1) where index is a negative number. This is because the Java-written Binary Search returns -index-1 if it does not find the element, where index is where the element would be if it existed in the array/collection. This way you shift the add time complexity to O(log(n)) and your searching time complexity is also O(log(n)), which means you take less performance hit when searching, but more performance hit when adding elements.
 
Piet Souris
Bartender
Posts: 4676
183
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Splendid idea! In the second case I would use a List. Chances are that you do not know upfront how many elements will be added, and inserting into a List will make Java do all the shifting.
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic