Give the asymptotic running time of each the following functions in Theta notati

Question

Give the asymptotic running time of each the following functions in Theta notation. Justify your answer. (Show your work.) WRITE YOUR ANSWERS ON A SEPARATE SHEET OF LINED PAPER DO NOT HAND IN A MARKED UP QUESTION SHEET func1(n) s leftarrow 0: for i leftarrow 27 to n^4 do for j rightarrow 111 to [i^2/3 (log_7 (i))^2] do s rightarrow s + i - j end end return (s): func2(n) s rightarrow 0: for i leftarrow 6 ro [n log_3 (n)] do j leftarrow i^3 while (j greaterthanorequalto i) do s leftarrow s + i - j + k: j leftarrow j - 14: end end return (s) func3(n) s leftarrow 0: for i leftarrow [n/2] to [n log_7 (n)] do for j leftarrow i to [log_7 (n)] do for k leftarrow 6j^2 to 6j^2 + [squareroot n] do s leftarrow s + i - j + k: end end end return (s): func4 (n) s leftarrow 0 for i leftarrow [(log_8 (n))^2 to [n^3/2 log_9 (n)] do for j leftarrow 1 to i^2 do for k leftarrow j to i^2 do s leftarrow s + i - j + k: end end return (s);

Explanation / Answer

Q1 func1(n)
1 s<-0;
2 for i<-27 to n4 do // loop1
3 for j<- 111 to [i2/3(log7(i))2] do // loop2
4 s<-s+i-j;
5 end
6 end
7 return(s);

asymptotic running time
Best Case
Line 1: 1
Line 2: 1
Line 3: 0 (if the condition of loop1 fails in first check then control wont be coming here)
Line 10: 1

hence: 1+1+0+1 => 3

Worst Case
Line 1: 1
Line 2: O(n)(normally loop execues n times since here its not mentioned the incrementor/decrementor so it will be assumed as n times increment )
Line 3: O(n) (normally loop execues n times since here its not mentioned the incrementor/decrementor so it will be assumed as n times increment )
Line 7: 1

hence: 1+O(n)*O(n)+ 1 => 2 + O(n2)

Q2 func2(n)
1 s<-0;
2 for i<-6 to [nlog3(n)] do // loop1
3 j<-i3;
4 while (j>=i) do // loop2
5 s<-s+i-j+k;
6 j<-j-14;
7 end
8 end
9 return(s);

asymptotic running time
Best Case
Line 1: 1
Line 2: 1
Line 3: 0 (if the condition of loop1 fails in first check then control wont be coming here)
Line 10: 1

hence: 1+1+0+1 => 3

Worst Case
Line 1: 1
Line 2: O(n)(normally loop execues n times since here its not mentioned the incrementor/decrementor so it will be assumed as n times increment )
Line 4: O(n) (normal incrementing as it is j=j-14 )
Line 9: 1

hence: 1+O(n)*O(n)+ 1 => 2 + O(n2)

Q3 func3(n)
1 s<-0;
2 for i<-[n/2] to [nlog7(n)] do // loop1
3 for j<- i to [nlog7(n)] do //loop2
4 for k<- 6j2 to 6j2 + [sqrt(n)] do //loop3
5 s<-s+i-j+k;
6 end
7 end
8 end
9 return(s);

asymptotic running time
Best Case
Line 1: 1
Line 2: 1
Line 3: 0 (if the condition of loop1 fails in first check then control wont be coming here)
Line 4: 0 (if the condition of loop1 fails in first check then control wont be coming here)
Line 10: 1

hence: 1+1+0+1 => 3

Worst Case
Line 1: 1
Line 2: O(n)(normally loop execues n times since here its not mentioned the incrementor/decrementor so it will be assumed as n times increment )
Line 3: O(n) (normally loop execues n times since here its not mentioned the incrementor/decrementor so it will be assumed as n times increment )
Line 4: O(n) (normally loop execues n times since here its not mentioned the incrementor/decrementor so it will be assumed as n times increment )
Line 9: 1

hence: 1+O(n)*O(n)*O(n)+ 1 => 2 + O(n3)

Q4 func4(n)
1 s<-0;
2 for i<-[log 8(n)2] to [n3/2log9(n)] do // loop1
3 for j<- 1 to [i2] do //loop2
4 for k<- j to i2 + [sqrt(n)] do //loop3
5 s<-s+i-j+k;
6 end
7 end
8 end
9 return(s);

asymptotic running time
Best Case
Line 1: 1
Line 2: 1
Line 3: 0 (if the condition of loop1 fails in first check then control wont be coming here)
Line 4: 0 (if the condition of loop1 fails in first check then control wont be coming here)
Line 10: 1

hence: 1+1+0+1 => 3

Worst Case
Line 1: 1
Line 2: O(n)(normally loop execues n times since here its not mentioned the incrementor/decrementor so it will be assumed as n times increment )
Line 3: O(n) (normally loop execues n times since here its not mentioned the incrementor/decrementor so it will be assumed as n times increment )
Line 4: O(n) (normally loop execues n times since here its not mentioned the incrementor/decrementor so it will be assumed as n times increment )
Line 9: 1

hence: 1+O(n)*O(n)*O(n)+ 1 => 2 + O(n3)

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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