Databases
StackOverflow2013
Postsdbo
POTime Analysis of Tower of Hanoi in Java
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POTime Analysis of Tower of Hanoi in Java
    primarykey
    data
    text
    <p>I was just testing <strong>Towers of Hanoi</strong> problem in <strong>Java</strong> and I ran the following code: (I have removed <code>sysouts</code> for convinience)</p> <pre><code>public class Util { public static void main(String[] args) { for (int i = 1; i &lt;= 30; i++) { long startTime = System.currentTimeMillis(); solveTowerOfHanoi(i, "A", "B", "C"); System.out.println("Time taken for " + i + ": " + (System.currentTimeMillis() - startTime)); } } public static void solveTowerOfHanoi(int n, String src, String inter, String dest) { if (n == 0) { return; } solveTowerOfHanoi(n - 1, src, dest, inter); solveTowerOfHanoi(n - 1, inter, src, dest); } } </code></pre> <p>I did an experiment and I tried disk sizes (indexes) from 1 to 35, ad I observed a very strange timing pattern, here is the output of the program:</p> <pre><code>Time taken for 1: 0 Time taken for 2: 0 Time taken for 3: 0 Time taken for 4: 0 Time taken for 5: 0 Time taken for 6: 0 Time taken for 7: 0 Time taken for 8: 1 Time taken for 9: 0 Time taken for 10: 0 Time taken for 11: 0 Time taken for 12: 0 Time taken for 13: 0 Time taken for 14: 0 Time taken for 15: 0 Time taken for 16: 0 Time taken for 17: 0 Time taken for 18: 3 Time taken for 19: 2 Time taken for 20: 11 Time taken for 21: 10 Time taken for 22: 39 Time taken for 23: 37 Time taken for 24: 158 Time taken for 25: 147 Time taken for 26: 603 Time taken for 27: 579 Time taken for 28: 2414 Time taken for 29: 2304 Time taken for 30: 9509 Time taken for 31: 9408 Time taken for 32: 38566 Time taken for 33: 37531 Time taken for 34: 152255 Time taken for 35: 148704 </code></pre> <p><strong>Question 1</strong>: The algorithm has exponential growth <em>(2^n-1)</em>, then why do I see no gradual time growth from 1-20? But then sudden jumps from 20-35? </p> <p><strong>Question 2</strong>: Also another thing which amazes me even more is the equality of times in pairs. Starting from 19, (19,20), (21,22), (23,24), (25,26) etc.... have comparable times. I cannot understand this, if the growth rate of the algorithm is indeed exponential, why does two indexes give almost comparable times and then sudden jump at the next index?</p> <p><strong>Note</strong>: I repeated this program 2-3 times and got almost comparable timings so you can take it as an average run.</p> <p><strong>EDIT</strong><br/> Tried <code>System.nanoTime()</code> and got following results:</p> <pre><code>Time taken for 1: 62644 Time taken for 2: 3500 Time taken for 3: 3500 Time taken for 4: 4200 Time taken for 5: 6300 Time taken for 6: 7350 Time taken for 7: 11549 Time taken for 8: 19948 Time taken for 9: 47245 Time taken for 10: 73142 Time taken for 11: 87491 Time taken for 12: 40246 Time taken for 13: 39196 Time taken for 14: 156784 Time taken for 15: 249875 Time taken for 16: 593541 Time taken for 17: 577092 Time taken for 18: 2318166 Time taken for 19: 2305217 Time taken for 20: 9468995 Time taken for 21: 9082284 Time taken for 22: 37747543 Time taken for 23: 37230646 Time taken for 24: 150416580 Time taken for 25: 145795297 Time taken for 26: 603730414 Time taken for 27: 578825875 Time taken for 28: 2409932558 Time taken for 29: 2399318129 Time taken for 30: 9777009489 </code></pre> <p>Output is almost similar to the millisecs, but it does make the picture clear...answers my <strong>Question 1</strong> may be, but <strong>Question 2</strong> is still intriguing. And <code>System.nanoTime()</code> raised one more question:</p> <p><strong>Question 3</strong>: Why does index 1 take more time than the next indexes (2,3...) etc ?</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USDhwaneet Bhatt
    1. USDhwaneet Bhatt
    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
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POTime Analysis of Tower of Hanoi in Java
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POTime Analysis of Tower of Hanoi in Java
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POTime Analysis of Tower of Hanoi in Java
      1. This table or related slice is empty.
      1. VTUpMod
    1. COTry with `System.nanoTime()` instead of `System.currentTimeMillis()` to count the process time.
      singulars
      1. POTime Analysis of Tower of Hanoi in Java
      1. USCrazenezz
    2. CO@Crazenezz: Used `System.nanoTime()` and captured the results, pleased read the results. Thanks for suggesting the **extra** research.
      singulars
      1. POTime Analysis of Tower of Hanoi in Java
      1. USDhwaneet Bhatt
    3. CODeclare startTime variable outside the for loop. you will always find exponential growth..
      singulars
      1. POTime Analysis of Tower of Hanoi in Java
      1. USAlpesh Prajapati
 

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