Larbi Ben M'hidi -Oum El Bouaghi- University
Faculty of Exact Sciences, Natural and Life Sciences
Department of Mathematics and Computer Science
level: 2nd Year of Bachelor degree in Computer Science- 3rd Semester (2025-2026)
Module: ADS 3
Tutorial 1
Exercise n° 1: For each of the following functions Ti(n), determine its asymptotic complexity
in Big-O notation. Example : T(n) =5n3+2n ∈ O(n3).
1. T1(n) = 5n4+8n3+3n2+2n+1
2. T2(n) = 7 log n +15n+8
3. T3(n) = 20n log n+4n2+6n3
4. T4(n) = 2n +log n+n2
5. T5(n) = 10 n2 +5n log n
6. T6(n) = k2 +10n
7. T6(n) = k2 +10
Exercise n° 2: How long does it take to execute an algorithm for a problem of size n that uses
3n3+2n operations, each taking 10−6seconds, for n=5, n=15, n=30 and n=40?
Exercise n° 3: Find the time complexity of the following recurrence relation:
4 T(n-1) if n>0
T(n) =
2 if n=0
Exercise n° 4: V is a vector of n integers and x an integer. We want to find the index of the
first occurrence of x in v, and return -1 if x does not exist in v. The search function below
provides the solution:
int search(int v[], int n, int x) {
int i = 0, found = 0;
while (i < n && !found) {
if (v[i] == x) found = 1;
i++;
}
if (!found) return -1;
else return i-1;
}
What is the number of operations performed in the best and worst cases?
1
Exercise n° 5: Consider two algorithms A1and A2 with their respective execution times
T1(n)= 2n2 +4n + 30 and T2(n)=12n +150
1. Determine the asymptotic complexity of both algorithms in Big-O notation. Which
algorithm has the better asymptotic complexity?
2. Show that your solutions are correct by specifying a c and n0 such that the following
relation is satisfied: O(f)={g ∣ ∃ c > 0: ∃ n0 > 0:∀n > n0:g(n) ≤ c * f(n)}
3. Calculate the execution times of both algorithms A1 and A2 for n=1, n=5, n=10, n=20,
and n=40
4. Sketch the curves of both functions T1(n) and T2(n) on the same graph.
5. For what lengths of data n is each of the algorithms most efficient?