Databases
StackOverflow2013
Postsdbo
POSpatial complexity estimative of a recursion function
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POSpatial complexity estimative of a recursion function
    primarykey
    data
    text
    <p>I'm learning algorithms and data structures and I'm now on the part of time and space complexity. </p> <p>I have to solve a problem and them tell (based on my code) the time and spatial complexity.</p> <p>This is the code:</p> <pre><code>public class B { public static int minSum = -1; public static void main(String[] args) { int objects, sumA = 0, sumB = 0; Scanner readInput = new Scanner(System.in); objects = readInput.nextInt(); int[] trunk = new int[objects]; if (objects == 0) { System.out.print(0 + "\n"); } else if (objects == 1) { trunk[0] = readInput.nextInt(); System.out.print(trunk[0] + "\n"); } else { for (int i = 0; i &lt; objects; i++) { trunk[i] = readInput.nextInt(); } bruteforce(trunk, sumA, sumB, 0); System.out.println(minSum); } } public static void bruteforce(int[] trunk, int sumA, int sumB, int index) { int partialDiff; if (minSum == 0) { System.out.println(minSum); System.exit(0); } else if (index == trunk.length) { partialDiff = Math.abs(sumA - sumB); if (partialDiff &lt; minSum || minSum == -1) { minSum = partialDiff; } } else { bruteforce(trunk, sumA + trunk[index], sumB, index + 1); bruteforce(trunk, sumA, sumB + trunk[index], index + 1); } } } </code></pre> <p>Basically the user first inputs a number of objects and then inputs, for each object, its value. The algorithm will distribute the objects by two bags and must calculate the min difference that can be calculated when distributing the objects by the two bags.</p> <p>I believe that it takes exponential time but I'm struggling with an estimative for the spatial complexity. Can you point me In some direction?</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USAralicia
    1. USFavolas
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POSpatial complexity estimative of a recursion function
      1. This table or related slice is empty.
      1. VTApproveEditSuggestion
    2. VO
      singulars
      1. POSpatial complexity estimative of a recursion function
      1. This table or related slice is empty.
      1. VTDownMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload