bccheatha Posted November 18, 2016 Share Posted November 18, 2016 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 More sharing options...
fiveworlds Posted November 18, 2016 Share Posted November 18, 2016 (edited) 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, 2016 by fiveworlds -1 Link to comment Share on other sites More sharing options...
Unity+ Posted November 19, 2016 Share Posted November 19, 2016 What is the logic behind having O(1) for the first coded problem? Link to comment Share on other sites More sharing options...
fiveworlds Posted November 19, 2016 Share Posted November 19, 2016 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 More sharing options...
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now