Jawaharlal Nehru Technological University Hyderabad B.Tech II DESIGN AND ANALYSIS OF ALGORITHMS Previous Question Paper (March - 2022 - R13)

Pseudocode is a high-level description of an algorithm that uses a mixture of natural language and programming constructs to convey the logic without adhering to the strict syntax of a specific language. The common conventions used include:

• Control Structures: Standard constructs like if-then-else, while, for, and repeat-until are used to manage flow.
• Assignment: The assignment operator is represented by the symbol ← (e.g., x ← y + z).
• Indexing: Arrays are typically indexed using square brackets, such as A[i], where the index can be a variable or expression.
• Method Calls: Procedures are invoked by name, with parameters passed by value or reference.
• Comments: Comments are usually indicated by double slashes (//) or specific delimiters to explain the purpose of blocks of code.
• Indentation: Block structure is defined by indentation rather than braces or keywords like 'begin' and 'end'.
• Data Types: Variables are not explicitly declared with types, as the focus is on the algorithmic logic rather than implementation details.

Binary search is an efficient divide-and-conquer algorithm used to find the position of a target value within a sorted array. It works by repeatedly dividing the search interval in half. If the target value is less than the item in the middle of the interval, the search continues in the lower half; otherwise, it continues in the upper half.

The time complexity is derived as follows:

• In each step, the algorithm compares the target with the middle element and discards half of the remaining elements.
• Let T(n) be the time taken for an array of size n. The recurrence relation is:

• Using the Master Theorem or repeated substitution, where T(1) = 1:
• T(n) = T(n/2) + 1
• T(n) = (T(n/4) + 1) + 1 = T(n/4) + 2
• T(n) = T(n/2^k) + k
• Setting n/2^k = 1, we get k = log_2(n).
• Therefore, T(n) = T(1) + log_2(n), which results in a time complexity of O(log n).