Algorithm Analysis and Design

If an algorithm has a loop that runs n times and performs O(1) operations in each iteration, what is the overall time complexity?

• O(1)

• O(n)

• O(n²)

• O(log n)

Consider the following code snippet:

for(int i = 0; i < n; i++) {

for(int j = 0; j < n; j++) {

cout << "Hello";

}

}

What is the time complexity?

• O(n)

• O(n log n)

• O(n²)

• O(n³)

What is the time complexity of the following algorithm?

int i = 1;

while (i < n) {

i = i * 2;

}

• O(n)

• O(log n)

• O(n log n)

• O(n²)

What is the time complexity of the recursive function below?

void func(int n) {

if (n <= 1) return;

func(n/2);

}

• O(n)

• O(log n)

• O(n log n)

• O(n²)

If a problem of size n is divided into two subproblems of size n/2 and combined in O(n) time, what is the overall time complexity using the Master Theorem?

• O(n log n)

• O(n²)

• O(n)

• O(log n)

What is the time complexity of inserting an element into a Binary Search Tree (BST) in the worst case?

• O(1)

• O(log n)

• O(n)

• O(n log n)

After inserting a new node in an AVL tree, which of the following operations might be required to maintain balance?

• Only Left Rotation

• Only Right Rotation

• Either Left or Right Rotation

• Left Rotation, Right Rotation, or Double Rotation

In a B-Tree of order m, how many keys can a node have at maximum?

• m

• m - 1

• 2m

• m + 1

Insertion in a Red-Black Tree may cause imbalance. What is the color of a newly inserted node before any rotations or recoloring?

• Black

• Red

• Depends on the parent node

• None of the above

What is the time complexity of inserting a string of length L into a Trie?

• O(1)

• O(log n)

• O(L)

• O(n L)