int s = 20; for(int i=1; i<n; i=i+2) for(int j=n; j>1; j=j/2){ s++; s =s *j; } f

Question

int s = 20; for(int i=1; i<n; i=i+2) for(int j=n; j>1; j=j/2){    s++; s =s *j; } for(int k=0; k<n*n; j++)    if (....) s=s*j;


Find best case and worst cases complexity int s = 20; for(int i=1; i<n; i=i+2) for(int j=n; j>1; j=j/2){    s++; s =s *j; } for(int k=0; k<n*n; j++)    if (....) s=s*j;


Find best case and worst cases complexity int s = 20; for(int i=1; i<n; i=i+2) for(int j=n; j>1; j=j/2){    s++; s =s *j; } for(int k=0; k<n*n; j++)    if (....) s=s*j; int s = 20; for(int i=1; i<n; i=i+2) for(int j=n; j>1; j=j/2){    s++; s =s *j; } for(int k=0; k<n*n; j++)    if (....) s=s*j;

Explanation / Answer

int s = 20;
for(int i=1; i<n; i=i+2) <<n/2 times>>
   for(int j=n; j>1; j=j/2){ <<log n/log 2 times>>
      s++;
   s =s*j;
}
for(int k=0; k<n*n; j++)   <<n*n times>>
    if (....)
       s=s*j;

Worst case time:

n/2 * log2 n + n2
= O(nlogn) + O(n2)
= O(n2)

Best case time:
n/2 * log2 n + n2
=(nlogn) + (n2) (considering that if statement does not impact the time)
= (n2)

considering if statement is the main time comsuming factor in k loop
n/2 * log2 n + 1
=(nlogn) + (1) (considering that if statement does not impact the time)
= (nlogn)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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