my computer science ii final tomorrow, , need understanding how find big-oh segments of code. i've searched internet , haven't been able find examples of how need understand it.
here's problem our sample final:
for(int pass = 1; <= n; pass++) { for(int index = 0; index < n; index++) for(int count = 1; count < n; count++) { //o(1) things here. } } } we supposed find order (big-oh) of algorithm.
i think o(n^3), , here how came conclusion
for(int pass = 1; <= n; pass++) // evaluates n times { for(int index = 0; index < n; index++) // evaluates n * (n+1) times for(int count = 1; count < n; count++) // evaluates n * n * (n) times { //o(1) things here. } } } // t(n) = (n) + (n^2 + n) + n^3 // t(n) = n^3 + n^2 + 2n // t(n) <= c*f(x) // n^3 + n^2 + 2n <= c * (n^3) // o(n) = n^3 i'm not sure if i'm doing correctly. can explain how evaluate code and/or confirm answer?
yes, o(n^3). however:
for(int pass = 1; pass <= n; pass++) // evaluates n times { //^^i should pass for(int index = 0; index < n; index++) //evaluates n times for(int count = 1; count < n; count++) // evaluates n-1 times { //o(1) things here. } } } since have 3 layer of nested loops, nested loop evaluated n *n * (n-1) times, each operation inside inner loop takes o(1) time, in total have n^3 - n^2 constant operations, o(n^3) in order of growth.
a summary of how measure order of growth in big o notation can found here:
quoting part above file:
nested loops
in 1 .. n loop j in 1 .. m loop sequence of statements end loop; end loop;the outer loop executes n times. every time outer loop executes, inner loop executes m times. result, statements in inner loop execute total of n * m times. thus, complexity o(n * m). in common special case stopping condition of inner loop
j <ninstead ofj <m(i.e., inner loop executes n times), total complexity 2 loops o(n^2).
similar rationale can applied in case.
Comments
Post a Comment