Computer Science and Numerical Methods Flashcards

What is the time complexity of binary search on a sorted array of n elements?

Answer: O(log n)

Binary search repeatedly halves the search space, resulting in a logarithmic number of comparisons — O(log n).

The Newton-Raphson iterative formula for finding the root of f(x) = 0 is:

Answer: x_(n+1) = x_n - f(x_n)/f'(x_n)

The Newton-Raphson method subtracts the ratio f(x_n)/f'(x_n) from the current estimate to converge toward the root.

What is the decimal equivalent of the binary number 1101?

Answer: 13

1101 in binary equals 1×8 + 1×4 + 0×2 + 1×1 = 8 + 4 + 0 + 1 = 13.

In numerical methods, the trapezoidal rule is used to approximate:

Answer: A definite integral

The trapezoidal rule approximates a definite integral by summing the areas of trapezoids formed under the curve.

Which data structure follows the LIFO (Last In, First Out) access principle?

Answer: Stack

A stack removes elements in the reverse order they were added, so the last element pushed is the first one popped.

The average-case time complexity of merge sort is:

Answer: O(n log n)

Merge sort divides the array into halves (log n levels) and merges them in O(n) per level, giving O(n log n) overall.

In programming, recursion is best described as:

Answer: A function that calls itself directly or indirectly

Recursion occurs when a function invokes itself with a modified argument, progressing toward a base case that terminates the calls.