Scribd
Upload
4 views1 page

Daa

This document provides definitions and explanations related to algorithms, including key concepts such as sorting, average case performance, Big 'O' notation, time complexity, spanning trees, recursive algorithms, and complexities of merge sort, quick sort, and binary search. It also defines what constitutes an optimal solution. Each question is structured to carry one mark, indicating a quiz or assessment format.

Uploaded by

4lbin007
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
4 views1 page

Daa

This document provides definitions and explanations related to algorithms, including key concepts such as sorting, average case performance, Big 'O' notation, time complexity, spanning trees, recursive algorithms, and complexities of merge sort, quick sort, and binary search. It also defines what constitutes an optimal solution. Each question is structured to carry one mark, indicating a quiz or assessment format.

Uploaded by

4lbin007
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd

PART A

(Each question carries 1 mark)

1. Define Algorithm:
An algorithm is a step-by-step procedure or set of rules to solve a specific
problem or perform a computation.

2. What is sorting?
Sorting is the process of arranging data in a specific order, such as ascending or
descending.

3. Write a short note on Average case:


The average case of an algorithm refers to the expected performance when the input
is randomly distributed.

4. Write a note on Big "O" notation:


Big "O" notation is a mathematical representation to describe the upper bound of an
algorithm's time or space complexity.

5. What do you mean by time complexity of an algorithm?


Time complexity is the amount of time an algorithm takes to run as a function of
the size of its input.

6. Define spanning tree:


A spanning tree is a subgraph of a connected graph that includes all vertices and
forms a tree.

7. What is recursive algorithm?


A recursive algorithm solves a problem by dividing it into smaller instances of the
same problem.

8. What is the complexity of merge sort and quick sort?

Merge sort: O(n log n)

Quick sort: Best/Average O(n log n) , Worst O(n^2)

9. What is the complexity of binary search?


O(log n)

10. Explain Optimal solution:


An optimal solution is the best possible solution to a problem, typically
minimizing or maximizing a specific metric.

You might also like