Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Time and Space complexity are different aspects of calculating the efficiency of an algorithm.</p> <blockquote> <p><strong>Time complexity</strong> deals with finding out how the computational time of an algorithm changes with the change in size of the input.</p> <p>On the other hand, <strong>space complexity</strong> deals with finding out how much (extra)space would be required by the algorithm with change in the input size.</p> </blockquote> <p>To calculate time complexity of the algorithm the best way is to check if we increase in the size of the input, will the number of comparison(or computational steps) also increase and to calculate space complexity the best bet is to see additional memory requirement of the algorithm also changes with the change in the size of the input.</p> <p>A good example could be of <a href="http://www.algolist.net/Algorithms/Sorting/Bubble_sort">Bubble sort</a>. </p> <p>Lets say you tried to sort an array of 5 elements. In the first pass you will compare 1st element with next 4 elements. In second pass you will compare 2nd element with next 3 elements and you will continue this procedure till you fully exhaust the list. </p> <p>Now what will happen if you try to sort 10 elements. In this case you will start with comparing comparing 1st element with next 9 elements, then 2nd with next 8 elements and so on. In other words if you have N element array you will start of by comparing 1st element with N-1 elements, then 2nd element with N-2 elements and so on. This results in <code>O(N^2)</code> time complexity. </p> <p>But what about size. When you sorted 5 element or 10 element array did you use any additional buffer or memory space. You might say <strong>Yes</strong>, I did use a temporary variable to make the swap. But did the number of variables changed when you increased the size of array from 5 to 10. No, Irrespective of what is the size of the input you will always use a single variable to do the swap. Well, this means that the size of the input has nothing to do with the additional space you will require resulting in <code>O(1)</code> or constant space complexity. </p> <p>Now as an exercise for you, research about the time and space complexity of <a href="http://www.shannarasite.org/kb/kbse30.html">merge sort</a></p>
    singulars
    1. This table or related slice is empty.
    1. PODifferences between time complexity and space complexity?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USPrateek
    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. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    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