Ask Question
22 October, 18:16

For each of the following six program fragments: a) Give an analysis of the running time (Big-Oh will do). b) Implement the code in the language of your choice, and give the running time for several values of N. c) Compare your analysis with the actual running times. (1) sum

+4
Answers (1)
  1. 22 October, 20:44
    0
    1) no of computations are:

    sum = 0 - (1 time)

    i=0 (1 times)

    i
    ++sum (n times)

    ++i (n times)

    Total = 3n+2

    O (n) is the big O notation

    2) no of computations are:

    sum = 0 - (1 time)

    i=0 (1 times)

    i
    ++sum (n^2 times)

    ++i (n times)

    j=0 (n times)

    j
    ++j (n^2 times)

    Total = 3n^2 + 3n+2

    O (n^2) is the big O notation as we considered the maximum possible computation

    3) no of computations are:

    sum = 0 - (1 time)

    i=0 (1 times)

    i
    ++sum (n^3 times)

    ++i (n times)

    j=0 (n times)

    j
    ++j (n^3 times)

    Total = 3n^3 + 3n+2

    O (n^3) is the big O notation as we considered the maximum possible computation

    4) no of computations are:

    sum = 0 - (1 time)

    i=0 (1 times)

    i
    ++i (n times)

    In the "j" th loop

    j=0 (n times)

    j
    Similarly + +j (n^2 times when i=n-1)

    Hence + +sum (n^2 times)

    Total = 3n^2 + 3n+2

    O (n^2) is the big O notation as we considered the maximum possible computation

    6) no of computations are:

    sum = 0 - (1 time)

    i=0 (1 times)

    i
    ++i (n times)

    In the "j" th loop

    j=0 (n times)

    j
    Similarly + +j (n^3 times when i=n-1)

    In the "k" th loop

    k=0 (max of n^3 times when j=n^3)

    k
    Similarly + +k (max of n^4 times when j=n^3)

    Finally + +sum (n^4 times when j=n^3)

    Total = 3n^4 + 3n^3+3n+2

    O (n^4) is the big O notation as we considered the maximum possible computation

    5) no of computations are:

    sum = 0 - (1 time)

    i=0 (1 times)

    i
    ++i (n times)

    In the "j" th loop

    j=0 (n times)

    j
    Similarly + +j (n^3 times when i=n-1)

    In the "k" th loop

    k=0 (max of n^3 times when j=n^3)

    k
    Similarly + +k (max of n^4 times when j=n^3)

    Finally + +sum (n^4 times when j=n^3)

    Total = 3n^4 + 3n^3+3n+2

    O (n^4) is the big O notation as we considered the maximum possible computation
Know the Answer?
Not Sure About the Answer?
Get an answer to your question ✅ “For each of the following six program fragments: a) Give an analysis of the running time (Big-Oh will do). b) Implement the code in the ...” in 📙 Computers & Technology if there is no answer or all answers are wrong, use a search bar and try to find the answer among similar questions.
Search for Other Answers