Jump to content

Determine the Big-O of Java code snips


bccheatha

Recommended Posts

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

Link to comment
Share on other sites

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 by fiveworlds
Link to comment
Share on other sites

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.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.