recategorized by
11,272 views
26 votes
26 votes

Which of the following statements is true?

  1. As the number of entries in a hash table increases, the number of collisions increases.

  2. Recursive programs are efficient

  3. The worst case complexity for Quicksort is $O(n^2)$

  4. Binary search using a linear linked list is efficient

  1. I and II
  2. II and III
  3. I and IV
  4. I and III
recategorized by

3 Answers

Best answer
46 votes
46 votes
Correct Option: D
Binary search using a linked list is not efficient as it will not give $O(\log n)$, because we will not be able to find the mid in constant time. Finding mid in linked list takes $O(n)$ time.
Recursive programs are not efficient because they take a lot of space, Recursive methods will often throw Stack Overflow Exception while processing big sets. moreover, it has its own advantages too.
edited by
2 votes
2 votes
We can solve it by elimination

Option II is not right because It require stack so these are not so efficient it eliminates A and B options

Option IV is wrong because in linked list worst case of find element is O(n) but in Binary Search worst case it is O(Log n) so it eliminates C

so correct answer is D
0 votes
0 votes

On Recursive programs are efficient or not?

The efficiency of recursive programs depends on various factors, and whether they are efficient or not can vary based on the problem at hand, the programming language used, and the specific implementation of the recursion. Here are some considerations:

  1. Clarity and Readability:

    • Recursive programs often provide clear and concise solutions to problems, especially those that naturally exhibit a recursive structure. The recursive structure can closely mirror the mathematical or logical nature of the problem, making the code easier to understand.
  2. Time Complexity:

    • In some cases, recursive solutions can have time complexities that are equivalent to their iterative counterparts. For example, algorithms like quicksort and mergesort can be implemented both recursively and iteratively with similar time complexities.
    • However, certain types of recursive algorithms might result in higher time complexity due to repeated calculations or redundant work.
  3. Space Complexity:

    • Recursive programs can sometimes have higher space complexity compared to their iterative counterparts because each recursive call adds a new layer to the call stack. This can lead to stack overflow errors for deep recursive calls.
    • Some recursive algorithms can be optimized to use tail recursion or dynamic programming techniques to reduce space complexity.
  4. Tail Recursion Optimization:

    • Some programming languages and compilers support tail call optimization, which can optimize certain recursive functions to use constant stack space. This can make recursive programs more memory-efficient.
  5. Function Call Overhead:

    • Recursive function calls generally have some overhead compared to iterative loops. The function call stack needs to manage parameters, local variables, and the return address for each recursive call.
  6. Iterative Alternatives:

    • In certain cases, an iterative solution might be more efficient and use less memory than its recursive counterpart. Some problems are more naturally expressed iteratively, and using recursion for such cases might lead to unnecessary complexity.
  7. Implementation Language:

    • The efficiency of recursive programs can also be influenced by the programming language and its support for recursion and optimization techniques.

In conclusion, whether recursive programs are efficient or not depends on the specific problem and how well the recursion is implemented. Recursive solutions can be elegant and intuitive but may require careful consideration of factors like time and space complexity. It's essential to analyze the characteristics of the problem and the specific implementation to determine the efficiency of a recursive solution.

Answer:

Related questions

49 votes
49 votes
7 answers
1
Kathleen asked Oct 8, 2014
38,083 views
The postfix expression for the infix expression $A+B*(C+D)/F+D*E$ is:$AB + CD + *F/D +E*$$ABCD + *F/DE* ++$$A * B + CD/F *DE ++$$A + *BCD/F* DE ++$
25 votes
25 votes
3 answers
2
Kathleen asked Oct 8, 2014
3,638 views
What is the number of binary trees with $3$ nodes which when traversed in post-order give the sequence $A, B, C ?$ Draw all these binary trees.
43 votes
43 votes
6 answers
3
Kathleen asked Oct 8, 2014
35,881 views
A binary tree $T$ has $n$ leaf nodes. The number of nodes of degree $2$ in $T$ is$\log_2 n$$n-1$$n$$2^n$
16 votes
16 votes
1 answer
4
Kathleen asked Oct 8, 2014
5,039 views
How many minimum spanning trees does the following graph have? Draw them. (Weights are assigned to edges).