Algorithms

Question 1

What is the time complexity of binary search?

Answer 1

O(log n) for a sorted array, as it halves the search space in each step.

Question 2

What is the difference between DFS and BFS?

Answer 2

Depth-First Search (DFS) explores as far as possible along a branch (uses stack/recursion). Breadth-First Search (BFS) explores level by level (uses queue). DFS: O(V+E), BFS: O(V+E).

Question 3

What is quicksort, and what is its average time complexity?

Answer 3

Quicksort partitions an array around a pivot, recursively sorting subarrays. Average: O(n log n), worst: O(n²) with poor pivot choice.

Question 4

What is dynamic programming?

Answer 4

A method to solve problems by breaking them into overlapping subproblems, storing results (memoization or tabulation) to avoid recomputation.

Example: Fibonacci in O(n).

Question 5

What is the time complexity of accessing an element in an array vs. a linked list?

Answer 5

Array: O(1) via index. Linked list: O(n) due to traversal.