Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Think of it like this. </p> <p>If you conisder multiplication between two numbers to be an operation that takes unit time. Then the complexity of a 2 number multiplication is done in theta(1) time. Now, in a for loop which runs for n-1 times for n numbers. You apply this operation n-1 times. So the theta(1) cost operation happens N-1 times which makes the overall cost of the operation theta(n-1) which in asymptotic terms is theta(n)</p> <p>The multiplication happens like this</p> <ul> <li>x=x </li> <li>x^2 = x*x </li> <li>x^3 = (x^2)*x </li> <li>x^4 = (x^3)*x </li> <li>................</li> <li>.................</li> <li>.................</li> <li>x^(n-1) =(x^(n-2))*x </li> <li>x^n = (x^(n-1))*x</li> </ul> <p>It's theta(1) for each step as you can use the result of a previous step to calculate the overall product. For example, when you caculate x^2. You can store the value of x^2 and use it while calculating x^3. Similarly when you calculate x^4 you can use the stored value of x^3.</p> <p>Now all the individual operations take theta(1) time. If you do it n times, the total time is theta(n). Now for calculating the complexity of x^n.</p> <ul> <li>for x^2, T(2) = theta(1)<br/> This is the base case for our induction.<br/></li> <li>Let us assume for x^k, T(k) = theta(k) to be true <br/></li> <li>x^(k+1) = (x^k)*x, T(k+1)= theta(k)+theta(1)</li> </ul> <p>Hence, for x^n, time complexity is T(n) = theta(N)</p> <p>and if you want to sum up the complexity. You are summing it up wrong.</p> <p>We know that T(2) = theta(1), time complexity of multiplying two numbers.</p> <ul> <li>T(n) = T(n-1)+T(2) (time complexity of multiplying two numbers and time complexity of multiplying (n-1) numbers)</li> <li>T(n) = T(n-2)+T(2)+T(2)</li> <li>T(n) = T(n-3)+T(2)+T(2)+T(2)</li> <li>...................</li> <li>...................</li> <li>T(n) = T(3) + (n-3)*T(2)</li> <li>T(n) = T(2) + (n-2)*T(2)</li> <li>T(n) = (n-1)*T(2)</li> <li>T(n) = (n-1)*theta(1)</li> <li>T(n) = theta(n)</li> </ul> <p>As you know C an example of how you will write a power(naive) function.</p> <pre><code> int power(int x,int n) { int powerVal=1; for(int i=1;i&lt;=n;++i) { powerVal=powerVal*x; } return powerVal; } </code></pre> <p>Now, as you can see each time multiplication of two integer takes place and that takes only theta(1) time. You run this loop n times. so total complexity is theta(n)</p>
    singulars
    1. This table or related slice is empty.
    1. POTime complexity of powering a number
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USerosenin
    1. USerosenin
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POTime complexity of powering a number
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI understand that doing individual operations n times will amount to theta(n). My question is rather simple, as stated in the comment in reply to Niet the Dark Absol. As we compute x^n starting from 1, then 1*x then 1*x*x, and the digits in x, x^2, x^3.... keep increasing, won't the time complexity be affected?
      singulars
      1. PO
      1. USuser720694
    2. CObingo. thanks for the explanation. Accepted.
      singulars
      1. PO
      1. USuser720694
    3. COJust reread your comment. Yes, they will be affected. But for simplicity's sake we consider the multiplication to be a single operation costing us theta(1) time. No matter how large the number.
      singulars
      1. PO
      1. USerosenin
 

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