I am very new to learning about Big-O so its still confusing to me. Could you please check my answers to these problems and perhaps give a me a nudge in the right direction on any that i got wrong. The ones involving code give me the most trouble.

 

1. What is the Big Oh of the following:
a. 4n^2 + 2 is: O(n^2) ?
b. n^2 + 14n + 6 is: O(n^2)
c. 5n^3 + 10n^2 – n – 8 is: O(n^3)
d. 3n^2 + 2n is: O(n^2)

 

I apologize for the poor formatting with the code.

 

3. int count = 0; O(1)
for (int i = 1; i <= n; i++) {
i = n; count += 1;
}
// end for

4. int total = 0; O(n^3)
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
for (int k = 1; three < j; j++) {
total += 1;
} //end for } // end for } // end for

5. int total = 0; O(n^3)
for (int one = 1; one <= n; one++) {
for (int two = 1; two < n; two++) {
for (int three = 1; three < 10; three++) {
total += 1;
} //end for } // end for } // end for

6. int total = 0; O(log n)
for (int pass = 1; pass <= n; pass*=2) {
total += 1;
}
// end for

7. p = n; O(n log n)
while (n>1) {
n = n/2;
while (p>0) {
p = p - 1;
}
// end while } // end while

8. for (int i = 1; i <= n; i+=2) { O(log n)
j=1;
while(j < n) {
j = j + 2; x = x + 2;
} // end while } // end for

a. 4n^2 + 2 is: O(1)
b. n^2 + 14n + 6 is: O(1)
c. 5n^3 + 10n^2 – n – 8 is: O(1)
d. 3n^2 + 2n is: O(1)

 

​Explain why the above is O(1) using CISC computer architecture. Explain why we don't use CISC architecture in relation to difficulty of design implementation.

 

​In a simple assignment function multiplying is a constant. In a risk architecture however the number is gotten through addition so therefore squaring a number takes a long time. Thing is you can also make a computer where addition takes a lot of time.

 

<script>
var s1 = 0, s2 = 0, s3 = 0;
var t1 = 0, t2 = 0, t3 = 0;
var test = Array();
test["000"] = 0;
test["001"] = 1;
test["010"] = 2;
test["011"] = 3;
test["100"] = 4;
test["101"] = 5;
test["110"] = 6;
test["111"] = 7;
for (var i = 0; i < 64; i = i + 1){

document.write(s1.toString(10)+s2.toString(10)+s3.toString(10)+t1.toString(10)+t2.toString(10)+t3.toString(10)+"="+test[s1.toString(10)+s2.toString(10)+s3.toString(10)]*test[t1.toString(10)+t2.toString(10)+t3.toString(10)]+"<br>");
s3=s3+1;
if(s3>1){s2=s2+1;s3=0;}
if(s2>1){s1=s1+1;s2=0;}
if(s1>1){t3=t3+1;s1=0;}
if(t3>1){t2=t2+1;t3=0;}
if(t2>1){t1=t1+1;t2=0;}

}

function multiply(a,b){
output = "overflow";
if (a + b == "000000"){output = 0;}
if (a + b == "001000"){output = 0;}
if (a + b == "010000"){output = 0;}
if (a + b == "011000"){output = 0;}
if (a + b == "100000"){output = 0;}
if (a + b == "101000"){output = 0;}
if (a + b == "110000"){output = 0;}
if (a + b == "111000"){output = 0;}
if (a + b == "000001"){output = 0;}
if (a + b == "001001"){output = 1;}
if (a + b == "010001"){output = 2;}
if (a + b == "011001"){output = 3;}
if (a + b == "100001"){output = 4;}
if (a + b == "101001"){output = 5;}
if (a + b == "110001"){output = 6;}
if (a + b == "111001"){output = 7;}
if (a + b == "000010"){output = 0;}
if (a + b == "001010"){output = 2;}
if (a + b == "010010"){output = 4;}
if (a + b == "011010"){output = 6;}
if (a + b == "100010"){output = 8;}
if (a + b == "101010"){output = 10;}
if (a + b == "110010"){output = 12;}
if (a + b == "111010"){output = 14;}
if (a + b == "000011"){output = 0;}
if (a + b == "001011"){output = 3;}
if (a + b == "010011"){output = 6;}
if (a + b == "011011"){output = 9;}
if (a + b == "100011"){output = 12;}
if (a + b == "101011"){output = 15;}
if (a + b == "110011"){output = 18;}
if (a + b == "111011"){output = 21;}
if (a + b == "000100"){output = 0;}
if (a + b == "001100"){output = 4;}
if (a + b == "010100"){output = 8;}
if (a + b == "011100"){output = 12;}
if (a + b == "100100"){output = 16;}
if (a + b == "101100"){output = 20;}
if (a + b == "110100"){output = 24;}
if (a + b == "111100"){output = 28;}
if (a + b == "000101"){output = 0;}
if (a + b == "001101"){output = 5;}
if (a + b == "010101"){output = 10;}
if (a + b == "011101"){output = 15;}
if (a + b == "100101"){output = 20;}
if (a + b == "101101"){output = 25;}
if (a + b == "110101"){output = 30;}
if (a + b == "111101"){output = 35;}
if (a + b == "000110"){output = 0;}
if (a + b == "001110"){output = 6;}
if (a + b == "010110"){output = 12;}
if (a + b == "011110"){output = 18;}
if (a + b == "100110"){output = 24;}
if (a + b == "101110"){output = 30;}
if (a + b == "110110"){output = 36;}
if (a + b == "111110"){output = 42;}
if (a + b == "000111"){output = 0;}
if (a + b == "001111"){output = 7;}
if (a + b == "010111"){output = 14;}
if (a + b == "011111"){output = 21;}
if (a + b == "100111"){output = 28;}
if (a + b == "101111"){output = 35;}
if (a + b == "110111"){output = 42;}
if (a + b == "111111"){output = 49;}
return output;
}
document.write(multiply("110","011"));
</script>

Edited November 19, 20169 yr by fiveworlds

What is the logic behind having O(1) for the first coded problem?

What is the logic behind having O(1) for the first coded problem?

 

 

To demonstrate that multiplication can be done in O(1) on a complex instruction set processor and by extension using multiplying by an exponent can be too. However this is all old technology that is rarely used anymore because they are complicated circuits. Processor nowadays have billions of transistors. NO company is going to handwrite everything but CISC requires handwriting and thats a problem when a processor has billions of transitors from an economic standpoint. It is cheaper for intel etc to copy simple RISC instructions millions of times which has allowed for moore's law but not advances in CISC architecture.