Can I get some help with these Complexity Computation questions? I don\'t unders

Question

Can I get some help with these Complexity Computation questions? I don't understand the rules computing. Please explain what you did, I need to learn not simply get the answers, so please show all your work.

Compute Complexity from Pseudocode. Compute the running time TON) for the following two codes for any n 0; (a) int sum (int n) int sum n for (int i 0; i n i++) sum-sum/2 if (sum 1) tbreak; return sum; b) int sum (int n) int sum o; for (int i 0; ikn i i+k) for (int j30; jki;j++) t sum-sum-1; return sum; (c) int sum (int n) t int sum sum (n-1) +1; if (n 0) {return sum;

Explanation / Answer

a)
   int sum(int n){

       int sum = n; // this line takes constant time O(1)
       for(int i=0; i<n; i++){ // this will executes n times, so O(n)
           sum = sum/2; // O(1)
           if(sum == 1) //O(1)
               break;
       }

       return sum; // O(1)
   }

   So, T(n) = O(1) + O(n) => O(n)

b)
   int sum(int n){

       int sum = 0; // O(1)
       for(int i=0; i<n; i=i+k){ // O(n/k), because i is forwarding by k

           for(int j=0; j<i; j++){ // for each value of i, it executes i times
               sum = sum +1;
           }
       }

       return sum;
   }

   for i =0:
       inner for loop execute: 0 times
   for i = k:
       inner for loop execute: k times
   for i = 2k:
       inner for loop execute: 2k times
   for i = 3k:
       inner for loop execute: 3k times

   --------------------
   ---------------------
   for i = (n-k):
       inner for loop execute: (n-k) times

   T(n) = k + 2k + 3k + 4k + ...... n/k times
       T(n) = n/(2*k) (k + n-k) => arithemetic sum = (n/2)(first_term + last_term)
           => (n^2)/2k => O(n^2) (appromax)

c)
   int sum(int n){

       int sum = sum(n-1) + 1;
       if(n==0){
           return sum;
       }
   }

   T(n) = T(n-1) + O(1) => because sum = sum(n-1) + 1
       = T(n-2) + O(1) + O(1)
       = T(n-3) + O(1) + O(1) + O(1)
       = T(n-4) + O(1) + O(1) + O(1) + O(1)
       ----------------
       -----------
       = O(1) + O(1) + O(1) + O(1) + O(1) + O(1) +..........n times
       = O(n)

Note: O(1) => notation for constant time complexity (means not dependent on input size)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.