int s = 1; for (int i=0; i<n; i++) if ( ....) for(int j=0; j<n; j++) s=s*i-j; el

Q: int s = 1; for (int i=0; i

Outer loop definitely runs for n times. So best case and worst case complexity depends on the inner loop Worst case happens when the inner loop is run n times. So, time complexity there would be O(n * n) = O(n^2) Best case happens when the inner loop enters else condition always where j is incremented by power of two and in that case inner loop runs log(n) times. So, time complexity there would be O(n * log(n)) = O(nlog(n))

ID: 3586762 • Letter: I

Question

int s = 1; for (int i=0; i<n; i++)    if ( ....) for(int j=0; j<n; j++) s=s*i-j; else for(int j=1; j<n; j=j*2)    s=s+i*j;
Find best case and worst cases complexity int s = 1; for (int i=0; i<n; i++)    if ( ....) for(int j=0; j<n; j++) s=s*i-j; else for(int j=1; j<n; j=j*2)    s=s+i*j;
Find best case and worst cases complexity int s = 1; for (int i=0; i<n; i++)    if ( ....) for(int j=0; j<n; j++) s=s*i-j; else for(int j=1; j<n; j=j*2)    s=s+i*j;
Find best case and worst cases complexity

Explanation / Answer

Outer loop definitely runs for n times. So best case and worst case complexity depends on the inner loop

Worst case happens when the inner loop is run n times. So, time complexity there would be O(n * n) = O(n^2)

Best case happens when the inner loop enters else condition always where j is incremented by power of two and in that case inner loop runs log(n) times. So, time complexity there would be O(n * log(n)) = O(nlog(n))

Navigate

int readFile(struct record ** ptrStart, char filename[ ]) { FILE * inFile = fope

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

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

int s = 1; for (int i=0; i<n; i++) if ( ....) for(int j=0; j<n; j++) s=s*i-j; el

Question

Explanation / Answer

Related Questions

Navigate