17 Questions
What is the time complexity of Linear Search?
O(n)
When does the Linear Search algorithm yield 'No match found'?
If no element is found equal to the key.
In the context of Linear Search, what does 'Auxiliary space' refer to?
Extra space used by the algorithm to perform the search.
What are the ideal applications of Linear Search?
Searching operations in smaller arrays.
How does the Linear Search algorithm determine a successful match?
When the key matches an element in the array.
Define space complexity.
Space complexity includes both Auxiliary space and space used by input.
What factors are used to compute space complexity?
Constant and instance characteristics.
Explain the space requirement formula S(p) = C + Sp.
S(p) = C + Sp where C is a constant fixed part and Sp denotes the space of inputs and outputs.
Provide an example algorithm and calculate its space complexity.
Algorithm add(a,b,c) { return a+b+c; } If a, b, c occupy one word size, the total size is 3.
Explain how Linear Search algorithm works.
Linear Search is a sequential search algorithm that checks each element of a list until the desired element is found or the end of the data set is reached.
What happens if the key is not found during a Linear Search?
The search continues till the end of the data set.
What is the time complexity of an algorithm that has a running time proportional to the square of the input size?
O(n^2)
Give an example of an algorithm associated with O(n^2) time complexity.
Selection sort
In the Selection Sort algorithm, what does the number of comparisons and swaps grow with as the size of the array increases?
Square of the input size
What is the time complexity of an algorithm that has a running time proportional to the cube of the input size?
O(n^3)
Give an example of an algorithm associated with O(n^3) time complexity.
Naive matrix multiplication
What type of algorithms often have triple nested loops and O(n^3) time complexity?
Less efficient algorithms
Learn about space complexity in algorithms, including auxiliary space and space used by input. Explore how to compute space complexity using factors like constant and instance characteristics, with a fixed part denoting inputs and outputs.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free
