Arab Academy for Science Technology and Maritime Transport
College of Computing and Information Technology
Course Computing Algorithms
Lecturer Dr Nahla Belal
GTA Maram
AsmaaShouman
Ossama
Sheet 1
Question 1:
Which kind of growth best characterizes each of these functions?
Constant Linear Polynomial Exponential
𝐧
𝟐 O O O O
(𝟑/𝟐)𝐧 O O O O
𝟏𝟎𝟎𝟎 O O O O
𝟑𝐧 O O O O
𝟐𝐧𝟑 O O O O
𝟏 O O O O
𝟑𝐧𝟐 O O O O
(𝟑/𝟐)𝒏 O O O O
Question 2:
Rank these functions according to their growth, from slowest growing (at the top)
to fastest growing (at the bottom).
𝟐𝒏 , 𝐧𝟐 , 𝐧𝟑 , (𝟑/𝟐)𝒏 , 𝒏, 𝟏
Rank these functions according to their growth, from slowest growing to fastest
growing
𝟖𝐧𝟐 , 𝟔𝐧𝟑 , 𝟒𝐧, 𝟖𝟐𝒏 , n log 6 n, nlog 2n, log 2n
Question 3:
Match each function with an equivalent function, in terms of their O. Only match a
function if f(n)=O(g(n))
F(n) g(n)
𝐧 + 𝟑𝟎 𝐧4
𝐧𝟐 + 𝟐𝐧 − 𝟏𝟎 3n − 1
𝐧𝟑 ∗ 𝟑𝐧 𝐧2 + 3n
Log2x Log22x
Question 4:
Choose all that apply:
1. For the functions, nK, and cn, what is the asymptotic relationship between these
functions? Assume that k >= 1 and c > 1 are constants.
a. nk is O(cn)
b. nk is 𝛀(cn)
c. nk is 𝜃(cn)
2. For the functions, lgn and log8n what is the asymptotic relationship between these
functions?
a. lgn is O( log8n)
b. lgn is 𝛀( log8n)
c. lgn is 𝜃( log8n)
3. What is the asymptotic relationship between the function n3lgn and 3nlog8n?
a. n3 lgn is O (3nlog8n)
b. n3 lgn is 𝛀 (3nlog8n)
c. n3 lgn is 𝜃 (3nlog8n)
4. You have an array containing the prime numbers from 2 to 311 in sorted order: [2, 3, 5, 7, 11, 13,
..., 307, 311]. There are 64 items in the array. About how many items of the array would binary
search have to examine before concluding that 52 is not in the array, and therefore not prime?
a. 32
b. 128
c. 7
d. 64
e. 1
f. 22
g. 11
5. For the functions, 8n and 4n, what is the asymptotic relationship between these functions?
a. 8n is O (4n)
b. 8n is 𝛀 (4n)
c. 8n is 𝜃 (4n)
6. 32 teams qualified for the 2014 World Cup. If the names of the teams were arranged in sorted
order (an array), how many items in the array would binary search have to examine to find the
location of a particular team in the array, in the worst case?
a. At most, 16.
b. At most, 32.
c. At most, 6.
d. At most, 1.
7. For the functions, lg nlg17 vs. lg17lgn what is the asymptotic relationship between these
functions?
b. lg nlg17 is O( lg17lgn)
c. lg nlg17 is 𝛀 (lg17lgn)
d. lg nlg17 is Θ (lg17lgn)
Question 5:
Fill in the following table by selecting one of the following: f(n) = O(g(n)), f(n) =
Ω(g(n)), or f(n) = Θ(g(n)). (log n = log2 n).
f(n) g(n)
3
n n6
n3 n3log n
n3 2n log n
n3 n2n
𝑛
n3 22
n6 n3log n
n6 2n log n
n6 n2n
𝑛
n6 22
n3log n 2n log n
n3log n n2n
𝑛
n3log n 22
2n log n n2n
𝑛
2n log n 22
𝑛
n2n 22
Question 6:
2. Prove the following:
𝑛2
a) 10
+ 2𝑛 = 𝑂(2𝑛 )
1
b) 21 + 𝑛 = 𝑂(1)
c) 10𝑙𝑜𝑔3𝑛 = 𝑂(𝑛)
d) log n3 = O(log n)
e) (O(n)+102) = O(n)
Question 7:
Describe an O(n log n)-time algorithm that, given a set S of n integers and another integer k,
determines whether or not there exists two elements in S whose sum is exactly k.
Question 8:
Describe an O (log n)-time algorithm that finds xn.
Question 9:
Describe an algorithm that performs matrix transposition for an n x n matrix. Transposition is
defined as interchange of the elements a ij and a ji , for i = 1, 2, ..., n and j = 1, 2, ..., n-1. Analyze the
time and space complexity of your algorithm.
Question 10:
Describe an O(1)-time algorithm that Count the total of 1 + 2 + . . . + n.
Question 11:
What is the time complexity of the following algorithms?
Part 1:
int t=0;
for(int i=1; i<=n; i++)
for(int j=0; j*j<4*n; j++)
for(int k=1; k*k<=9*n; k++)
t++;
Part 2:
int x=0;
for(int i=4*n; i>=1; i--)
x=x+2*i;
Part 3:
int z=0;
int x=0;
for (int i=1; i<=n; i=i*3){
z = z+5;
z++;
x = 2*x;
}
Part 4:
int y=0;
for(int j=1; j*j<=n; j++)
y++;
Part 5:
int b=0;
for(int i=n; i>0; i--)
for(int j=0; j<i; j++)
b=b+5;
Part 6:
int y=1;
int j=0;
for(j=1; j<=2n; j=j+2)
y=y+i;
int s=0;
for(i=1; i<=j; i++)
s++;
Part 7:
int b=0;
for(int i=0; i<n; i++)
for(int j=0; j<i*n; j++)
b=b+5;
Part 8:
int x=0;
for(int i=1; i<=n; i=i*3){
if(i%2 != 0)
for(int j=0; j<i; j++)
x++;}
Part 9:
for(int i =0 ; i < =n ; i++)
for (int j =1; j<= i * i; j++)
if (j % i == 0)
for (int k = 0; k<j; k++)
sum++;
Part 10:
int a = 0;
int k = n*n;
while(k > 1){
for (int j=0; j<n*n; j++)
{ a++; }
k = k/2;}
Part 11:
int fun(int n)
{ int count = 0;
for (int i = n; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count += 1;
return count;
}
Part 12:
int fun(int n)
{ int count = 0;
for (int i = 0; i < n; i++)
for (int j = i; j > 0; j--)
count = count + 1;
return count;
}
Part 13:
int n, rev;
rev = 0;
while (n > 0)
{ rev = rev*10 + n%10;
n = n/10;
}
Part 14:
int unknown(int n) {
int i, j, k = 0;
for (i = n/2; i <= n; i++)
for (j = 2; j <= n; j = j * 2)
k = k + n/2;
return k;
}
Part 15:
for (i = n, j = 0; i >0; i /= 2, j += i);
Part 16:
int fun1 (int n)
{int i, j, k, p, q = 0;
for (i = 1; i<n; ++i)
{ p = 0;
for (j=n; j>1; j=j/2)
++p;
for (k=1; k<p; k=k*2)
++q;}
return q; }
Part 17:
void fun()
{
int i, j;
for (i=1; i<=n; i++)
for (j=1; j<=log(i); j++)
printf("GeeksforGeeks");
}
Part 18:
int i=0, j=0, y=0, s=0;
for(j=0; j<n+1; j++)
y=y+j;
for(i=1; i<=y; i++)
s++;
Part 19:
m=a
i=1
while ( i <= n ) do
m=m*b
for i = 1 to m do
S
end for
end while
end
//S is O(1).
Part 20:
int i=1, z=0;
while( z < n*(n+1)/2 )
{
z+=i; i++;
}
Question 12:
For each of the following statements indicate whether it is true or false and
correct the false statements:
a. 2n3 +5n2 +log2n = 𝛀 (n2)
b. 3nlog2n +n51 = o(n51)
c. nlog2n +1 +2n2 = 𝛉 (n2)
d. 6n10 +n2 +3 = O(n10)
e. 6n10 +n2 +3 = o(n10)
f. (3/2)n √𝒏 + 5n2 +log2n = 𝛀 (n2√𝒏)
g. 2n3 + 5n2 + log2n = 𝛀 (n2)
h. 4nlog2n +10n2 +3 = 𝛉 (n logn)
i. (3/2)n √𝒏 + 5n2 +log2n = o (n3)
j. Log2(n6) + 7 + 4log3n = 𝛉 (logn)
k. 2n2 +nlog2n + 1 = 𝛉 (n3)
l. nlog23 = o (3 log2n)
m. 10+ n +n2 =O(n2)
n. 10+ n +n2 = 𝛉 (n2)
o. 10+ n +n2 = 𝛀 (n)
p. 10+ n +n2 = 𝛉 (n)
q. 10+ n +logn = 𝛀 (n)
r. 10+ n +logn = 𝐎 (n2)
s. 7 log2n +2 n logn = O(n)
t. 7 log2n +2 n logn = 𝛀 (logn)
u. (1/3)n +100 = O(1)
v. 3n + 100 = O (1)
w. 2n + 100 n2 + n100 = O(n101)