MathB.in - Share Mathematics with LaTeX and Markdown

<p>
for ( i = 1 to n )<br>
   for( j = 1 to $\lfloor i/2\rfloor$ )<br>
      x++

<table border="1" bordercolor="#FFCC00" style="background-color:#FFFFCC" width="100%" cellpadding="3" cellspacing="3">
  <tbody>
    
    <tr>
      <th>n</th>
      <th>i</th>
      <th>$\lfloor i/2\rfloor$</th>
      <th>j</th>
      <th>#exec</th>
    </tr>
    <tr>
      <td>1</td>
      <td>1</td>
      <td>0</td>
      <td>0</td>
      <td>0</td>
    </tr>
    <tr>
      <td>2</td>
      <td>2</td>
      <td>1</td>
      <td>2*1</td>
      <td>2</td>
    </tr>
    <tr>
      <td>3</td>
      <td>3</td>
      <td>1</td>
      <td>3*1</td>
      <td>3</td>
    </tr>
    <tr>
      <td>4</td>
      <td>4</td>
      <td>2</td>
      <td>4*2</td>
      <td>8</td>
    </tr>
    <tr>
      <td>5</td>
      <td>5</td>
      <td>2</td>
      <td>5*2</td>
      <td>10</td>
    </tr>
    <tr>
      <td>6</td>
      <td>6</td>
      <td>3</td>
      <td>6*3</td>
      <td>18</td>
    </tr>
    <tr>
      <td>7</td>
      <td>7</td>
      <td>3</td>
      <td>7*3</td>
      <td>21</td>
    </tr>
    <tr>
      <td>8</td>
      <td>8</td>
      <td>4</td>
      <td>8*4</td>
      <td>32</td>
    </tr>
  </tbody>
</table>

<br>
The number of executions looks very logarithmic to me, but it seems that the number of times x is incremented is $n * \lfloor (n/2)\rfloor$. Does that mean the function is running in $\Theta(n^2)$ or did I make a miscalculation?

Fri, 16 Nov 2012 03:12 GMT