Awesome q2a theme
0 votes
4 views

Huffman coding is a lossless data compression algorithm. The most frequent character gets the smallest code and the least frequent character gets the largest code. Consider the following statements regarding Huffman coding algorithm?
S1 : The time complexity of the Huffman algorithm is O(nlogn). Using a heap to store the weight of each tree, each iteration requires O(logn) time to determine the cheapest weight and insert the new weight. There are O(n) iterations, one for each item.
S2 : If the input array is sorted, there exists a linear time algorithm.
S3 : A divide-and-conquer approach might have us asking which characters should appear in the left and right subtrees and trying to build the tree from the top down. As with the optimal binary search tree, this will lead to to an exponential time algorithm.

Which of the following option is correct?
(A) Statement S1 is correct, Statements S2 and S3 are not correct.
(B) Statements S1 and S2 are correct and statement S3 is not correct.
(C) Statements S2 and S3 are correct and statement S1 is not correct.
(D) All statements S1, S2, and S3 are correct.

I am not getting proper explanation on Geekforgeeks for this question.

ago in Algorithms by (7 points) | 4 views

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users 2020 Aug 03 - 09
  1. Mellophi

    97 Points

  2. Ashutosh07091999

    69 Points

  3. prakhar2810

    7 Points

  4. Kushagra गुप्ता

    7 Points

  5. srestha

    7 Points

  6. kuldeep kumar07

    6 Points

  7. toppoavinash

    6 Points

  8. Shoaib_Ahmed

    6 Points

  9. prashastinama

    6 Points

  10. Aditi0103

    6 Points

Weekly Top User (excluding moderators) will get free access to GATE Overflow Test Series for GATE 2021
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Aug 2020
  1. Mellophi

    103 Points

  2. Ashutosh07091999

    72 Points

  3. Shaik Masthan

    13 Points

  4. srestha

    9 Points

  5. Unnayan kumar

    8 Points

  6. prakhar2810

    7 Points

  7. Sourav Kar

    7 Points

  8. anurag_yo

    7 Points

  9. Kushagra गुप्ता

    7 Points

  10. kuldeep kumar07

    6 Points

7,709 questions
1,823 answers
11,131 comments
95,090 users