Complexity Analysis Determine the worst case time complexity of the following al

Question

Complexity Analysis

Determine the worst case time complexity of the following algorithms. Express your final answer using Big-O notation
and justify all of your calculations

1. Algorithm MakeThumbnail(image, n)
-- Create a small 10x10 image from a larger image
Pre: image :: a 2D array of size n x n representing a greyscale image
n :: Integer, n >= 10
Return: a 10x10 thumbnail representation of the input image
int thumbnail[10][10]
i = 0
while (i < n)
j = 0
while (j < n)
thumbnail[i/10][j/10] matrix[i][j]
j = j + (n/10)
done
i = i + (n/10)
done
return thumbnail

2. Algorithm countTwos(n)
-- Count the number of occurrences of the number 2 in
prime factorizations of all numbers from 2 to n (inclusive)
Pre: n :: Integer, n >= 2
Return: the count of occurrences of 2
count = 0
i = 2
while (i <= n)
currentInt = i
while (currentInt % 2 == 0)
count = count + 1
currentInt = currentInt / 2
done
i = i + 1
done
return count

Explanation / Answer

both O(n^2)

since they have two while loops n*n

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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