Databases
StackOverflow2013
Postsdbo
POHow do I find the time complexity T(n) and show that it is tightly bounded (Big Theta)?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow do I find the time complexity T(n) and show that it is tightly bounded (Big Theta)?
    primarykey
    data
    text
    <p>I'm trying to figure out how to give a worst case time complexity. I'm not sure about my analysis. I have read nested <code>for</code> loops big O is <code>n^2</code>; is this correct for a <code>for</code> loop with a <code>while</code> loop inside?</p> <pre><code>// A is an array of real numbers. // The size of A is n. i,j are of type int, key is // of type real. Procedure IS(A) for j = 2 to length[A] { key = A[ j ] i = j-1 while i&gt;0 and A[i]&gt;key { A[i+1] = A[i] i=i-1 } A[i+1] = key } </code></pre> <p>so far I have: </p> <pre><code>j=2 (+1 op) i&gt;0 (+n ops) A[i] &gt; key (+n ops) so T(n) = 2n+1? </code></pre> <p>But I'm not sure if I have to go inside of the <code>while</code> and <code>for</code> loops to analyze a worse case time complexity... </p> <p>Now I have to prove that it is tightly bound, that is Big theta.</p> <p>I've read that nested <code>for</code> loops have Big O of <code>n^2</code>. Is this also true for Big Theta? If not how would I go about finding Big Theta?!</p> <p>**C1= C sub 1, C2= C sub 2, and no= n naught all are elements of positive real numbers</p> <p>To find the <code>T(n)</code> I looked at the values of <code>j</code> and looked at how many times the while loop executed:</p> <pre><code>values of J: 2, 3, 4, ... n Loop executes: 1, 2, 3, ... n </code></pre> <p>Analysis:<br> Take the summation of the while loop executions and recognize that it is <code>(n(n+1))/2</code> I will assign this as my <code>T(n)</code> and prove it is tightly bounded by <code>n^2</code>. That is <code>n(n+1)/2= θ(n^2)</code></p> <p>Scratch Work:</p> <pre><code>Find C1, C2, no є R+ such that 0 ≤ C1(n^2) ≤ (n(n+1))/2 ≤ C2(n^2)for all n ≥ no To make 0 ≤ C1(n) true, C1, no, can be any positive reals To make C1(n^2) ≤ (n(n+1))/2, C1 must be ≤ 1 To make (n(n+1))/2 ≤ C2(n^2), C2 must be ≥ 1 </code></pre> <p>PF:</p> <pre><code>Find C1, C2, no є R+ such that 0 ≤ C1(n^2) ≤ (n(n+1))/2 ≤ C2(n^2) for all n ≥ no Let C1= 1/2, C2= 1 and no = 1. </code></pre> <ol> <li><p>show that 0 ≤ C1(n^2) is true C1(n^2)= n^2/2<br> n^2/2≥ no^2/2<br> ⇒no^2/2≥ 0<br> 1/2 > 0<br> Therefore C1(n^2) ≥ 0 is proven true! </p></li> <li><p>show that C1(n^2) ≤ (n(n+1))/2 is true C1(n^2) ≤ (n(n+1))/2<br> n^2/2 ≤ (n(n+1))/2 n^2 ≤ n(n+1)<br> n^2 ≤ n^2+n<br> 0 ≤ n </p> <p>This we know is true since n ≥ no = 1<br> Therefore C1(n^2) ≤ (n(n+1))/2 is proven true! </p></li> <li><p>Show that (n(n+1))/2 ≤ C2(n^2) is true (n(n+1))/2 ≤ C2(n^2)<br> (n+1)/2 ≤ C2(n)<br> n+1 ≤ 2 C2(n)<br> n+1 ≤ 2(n)<br> 1 ≤ 2n-n<br> 1 ≤ n(2-1) = n<br> 1≤ n<br> Also, we know this to be true since n ≥ no = 1 </p> <p>Hence by 1, 2 and 3, θ(n^2 )= (n(n+1))/2 is true since<br> 0 ≤ C1(n^2) ≤ (n(n+1))/2 ≤ C2(n^2) for all n ≥ no </p></li> </ol> <p>Tell me what you thing guys... I'm trying to understand this material and would like y'alls input!</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USMansfield
    1. USEllen
    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
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHow do I find the time complexity T(n) and show that it is tightly bounded (Big Theta)?
      1. This table or related slice is empty.
      1. VTDownMod
    2. VO
      singulars
      1. POHow do I find the time complexity T(n) and show that it is tightly bounded (Big Theta)?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POHow do I find the time complexity T(n) and show that it is tightly bounded (Big Theta)?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThat's quite the title you got there. Is there _any_ way you could have included that content in the actual question itself??
      singulars
      1. POHow do I find the time complexity T(n) and show that it is tightly bounded (Big Theta)?
      1. USbedwyr
    2. COTry this tutorial: http://quizgen.org/tut/q12.BigOh.p4.pdf.
      singulars
      1. POHow do I find the time complexity T(n) and show that it is tightly bounded (Big Theta)?
      1. USBobbyShaftoe
    3. CO@Daniel L, Many thanks for your edits. =]
      singulars
      1. POHow do I find the time complexity T(n) and show that it is tightly bounded (Big Theta)?
      1. USstrager
 

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