a) Given an unsorted array A of integers of any size, n 3, and an integer value
ID: 3750047 • Letter: A
Question
a) Given an unsorted array A of integers of any size, n 3, and an integer value x, write an algorithm as a pseudo code (not a program!) that would find out if there exist EXACTLY 3 occurrences in the array with value x.
b) What is the time complexity of your algorithm, in terms of Big-O?
c) What is the space complexity of your algorithm, in terms of Big-O?
d) Will time complexity change if A was given as a sorted array? If yes; give a new algorithm that achieves this better complexity (indicate the time complexity as of that algorithm). If no, explain why such new constraints/conditions cannot lead to a better time complexity.
Explanation / Answer
ALGORITHM:
Boolean CountOccurence(int x)
{
iterate the array using for loop as
for( i =0; i< arrayLength; i++ )
{
if( array[ i ] ==x)
count++;
if(count==3)
return true;
}
return false;
}
ANSWER (b): Here Time complexity for my algorithm in the worst case will be as O(N) where N is the size of the array it is because if the element required to be searched in the array is present in the last position then we have to iterate the loop till the end.
ANSWER (C): Typically, to measure space complexity, you want to look at how much extra space is required to hold all the information necessary to execute the code.so here space complexity will be O(1) due to using the variable i in the for loop.
ANSWER (D): If you sort the array then in the worst case time complexity will be O(N) because suppose in the worst case the element you are searching the is present in the last index then you have to iterate the whole array. and in the best case if your element present at the initial indexes then it will take constant time.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.