Homework SourseWhat is the BigO Running time AND Space Complexity of each o
What is the Big-O Running time AND Space Complexity of each of the following algorithms? Explain why? Remember, express Big-O of both Running Time and Space Complexity of each algorithm. For each, justify your answer in short. a) incrementArray(int[1..n] A) { for (int i=0; i < 1000000; i=i+1) { A[i%n] = A[i%n] + 1 } } b) mysteryFunction(int n) { int r = 0; while (n>0) { n = n /10; r = r + 1; } } c) dummyFucntion (int [1..n] A) { int[] B = new int[n]; for (int i=0; i < n; i=i+1) { for (int j=0; j < n; j=j+1) { for (int k=0; k < n; k=k+1) { B[k] = A[k] + 10 } } } }
Solution
Answer to bit (a)
incrementArray(int[1..n] A)
{
for (int i=0; i < 1000000; i=i+1)
{
A[i%n] = A[i%n] + 1
}
}
Space complexity : The function requires an integer array A of length ‘n’ and a iterator ‘i’. Total number of memory space used =n+1 .
Assume an integer takes a 4 bytes of memory space. Total size of memory used is
S(n)=4(n+1)=4n+4 Bytes
=O(n) Bytes
Time Complexity: The runs loop 1000000+1 times .It does not depend on ‘n’.the line within the loop runs 1000000 times. So running time of the function is
T(n) = 1000000+1000000+1
=2000000+1
=O(1)
Answer to bit (b)
mysteryFunction(int n)
{
int r = 0; //line1
while (n>0) //line 2
{
n = n /10; //line 3
r = r + 1; // line 4
}
}
Space complexity : The function uses two integer variable i ,e ‘n’ and ‘r’. Assuming integer takes 4 bytes, A total space requirement is 4*2=8 Bytes
S(n) =8 Bytes
=O(1) Bytes
Time Complexity:
Total steps count:
Line 1 is executed 1 time
Line 2 is executed Log10n +1 times : as each time n is decrements by n/10. So after Log10n steps value of n will be 0. Plus 1 is for extra check for falsity
Line 3 is executed Log10n times
Line 4 is executed Log10n times
So
T(n)= 3log10n+1
=O(log10n)
Answer to bit (c)
dummyFucntion (int [1..n] A)
{
int[] B = new int[n]; //line 1
for (int i=0; i < n; i=i+1) //line 2
{
for (int j=0; j < n; j=j+1) //line 3
{
for (int k=0; k < n; k=k+1) //line 4
{
B[k] = A[k] + 10 // line 5
}
}
}
}
Space complexity: int uses tow int array(A,B) each of size n,and 3 int variable i,j,k. A total of 3n+3 memory locations are used
So S(n) = 4(3n+3) bytes : integer takes 4 bytes
=12n+12 bytes
=O(n)
Time Complexity:
Line 1 is executed 1 time.
Line 2 is executed n+1 times (plus 1 for extra check when the condition is false)
Line 3 is executed n.(n+1) times
Line 4 is executed n.(n.(n+1)) times
Line 5 is executed n.n.n times
So total steps will be
T(n)=1+(n+1)+(n2+n)+(n3+n2)+n3
=2n3+2n2+2n+2
=O(n3)
