Question

1. Determine the appropriate big-o expression for each of the following functions, and put your answer in the table we have provided in section 2-1 of ps5_parti. We've included the answer for the first function. (Note: We're using the “ symbol to represent exponentiation.) a (n) = 5n + 1 b. b(n) = 5 - 10n - n^2 o c(n) = 4n + 2log (n) d. e. d(n) = 6nlog (n) + n^2 e(n) = 2n^2 + 3n^3 - 7n

Answer 1

1. Big-O notattion :

        We need to keep in mind that : c < log(n) < n < nlog(n) < n2 < n3 < ------- < nn < 2n < n!

        -- And in Big-O notation we include the highest term.

a) a(n) = 5n + 1 ==> O(n)

b) b(n) = 5 - 10n - n2 ==>   This gives a negative complexity, which will conflict the definition of Big-O

                                           , it works for positive values. There is no sense for a algorithm to have         

                                           negative time complexity.

c) c(n) = 4n + 2log(n) ==> O(n)

d) d(n) = 6nlog(n) + n2 ==> O(n2)

e) e(n) = 2n2 + 3n3 - 7n ==> O(n3)

2. Solution in the image below :

2. for (int i=0; i < 3; i++) { - 0 for (int j = 0; j<n; j++) { - ③ for (int k = 0; k< jj k++) { - ③ Count (2) - look o will run 3 times - look ② will run n times - look ② will run it 0 + 1 + 2 + ------ n-il => (n-1) (n-1+1) times = n²-n 2 times => count () will be called :-3n (n2-n) times! 2 = 3n3-3n times => 0 (n)

3. Solution in the image below :

3. for (int i=0; i<n; i++) { - ① for (int j =n; j>oj j =j/2) { - ② count(); looh ① will be carun a times - look @ will run it log(n) times Lysince, j is divided by 2 every time = count () will be called n log in) times => on log(n))