problem 1.
find the upper bound of the following
i. 𝑓(𝑛) = 3𝑛 + 8
ii. 𝑓(𝑛) = 𝑛2 + 1
iii. 𝑓(𝑛) = 𝑛4 + 100𝑛2 + 1
iv. 𝑓(𝑛) = 480
find the lower bound of the following
i. 𝑓(𝑛) = 5 𝑛2
ii. Prove Ω
iii. 𝑓(𝑛) = 𝑛5 + 30𝑛2 + 1
iv. 𝑓(𝑛) = 4𝑛
find the upper bound of the following
𝑛2 𝑛
i. 𝑓(𝑛) = −
2 2
ii. 𝑓(𝑛) = 𝑛2 + 500
iii. 𝑓(𝑛) = 30𝑛
iv. Prove that 𝑓(𝑛) = 25𝑛 is
Problem 2
i. A Club consists of 20 members, of which 9 are male and 11 are
female. Seven members will be selected to form an event-
planning committee. How many committees of 4 females and
3 males can be formed?
ii. How many 7-digit telephone numbers can be formed if the first
digit cannot be 0 or 1?
iii. Three hardcover books and 5 paperbacks are placed on a shelf.
How many ways can the books be arranged if all the hardcover
books must be together and all the paperbacks must be
together?
iv. How many permutations are there of the word” SCHOOL”?
v. In how many ways can a cricket eleven be chosen out of a batch of
15 players if
a) There is no restriction on the selection.
b)A Particular Player is always chosen.
c) A Particular Player is never chosen.
vii. Make all arrangement of letters of the word TAMIL so that
d) T is always next to L
e) T and L are always together
Problem 2
Find the time complexity of the following code snippets
for(i= 0 ; i < n; i++){
cout<< i << " " ;
i++;
}
Problem 3
Find the time complexity of the following code snippets
for(i= 0 ; i < n; i++){
for(j = 0; j<n ;j++){
cout<< i << " ";
}
}
Problem 4
Find the time complexity of the following code snippets
int i = n;
while(i){
cout << i << " ";
i = i/2;
}
Problem 5
Find the time complexity of the following code snippets
if(i > j ){
j>23 ? cout<<j : cout<<i;
}
Problem 6
Find the time complexity of the following code snippets
for(i= 0; i < n; i++){
for(j = 1; j < n; j = j*2){
cout << i << " ";
}
}
Problem 7
What is the time & space complexity of the following code:
let a = 0, b = 0;for (let i = 0; i < n; ++i) {
a = a + i;
}
for (let j = 0; j < m; ++j) {
b = b + j;
}
Problem 8
What is the time & space complexity of the following code:
let a = 0, b = 0;
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
a = a + j;
}
}
for (let k = 0; k < n; ++k) {
b = b + k;
}
Problem 9
What is the time and space complexity of the following code:
let a = 0;
for (let i = 0; i < n; ++i) {
for (let j = n; j > i; --j) {
a = a + i + j;
}
}
Problem 10
What is the time complexity of the following code:
for (let i = n; i > 0; i = parseInt(i / 2)) {
console.log(i);
}
Problem 11
What is the time complexity of the following code:
for (let i = 1; i < n; i = i * 2) {
console.log(i);
}
Problem 12
What is the time complexity of the following code:
for (let i = 0; i < n; ++i) {
for (let j = 1; j < n; j = j * 2) {
console.log(j);
}
}
Problem 13
Explain any four approach to algorithm design
