Key Concepts in Computer Science -Assignment 9

1) [6 marks] Show that each of these pairs of functions are of the same order.
We should show that each of these functions are big-Theta of each other. One way is to show that each of them is big-O of the other one and vice versa. We should find proper C and k of the big-O definition.
a) 3x + 2 and x
 3x + 2 is O(x): 3x + 2 ≤ 6x (x > 1) ⟹ C = 6 and k = 1
 x is O(3x + 2): x ≤ 3x + 2 (x > 1) ⟹ C = 1 and k = 1
b) 2×2 + 3x – 5 and x2
 2×2 + 3x – 5 is O(x2): 2×2 + 3x – 5 ≤ 10×2 (x > 1) ⟹ C = 10 and k = 1
 x2 is O(2×2 + 3x – 5): x2 ≤ x2 + x2 – 5 (x > 3) ⟹ x2 ≤ 2×2 – 5 ≤ 2×2 + 3x – 5 (x > 3) ⟹ C = 1 and k = 3
2) [12 marks] Determine whether x3 is O(g(x)) for each of these functions g(x).
a) g(x) = x2 x3 is not O(x2)
b) g(x) = x2 + x3 x3 is O(x2 + x3)
c) g(x) = 3x x3 is O(3x)
d) g(x) = x2 + x4 x3 is O(x2 + x4)
3) [8 marks] Find a C and k for big-O and plot the f(x) and C.g(x) function for f(x) = 2×2 – 3x + 4 and g(x) = x2. Assume x > 0
2×2 – 3x + 4 ≤ 9×2 (x > 1) ⟹ C = 9 and k = 1

4) [8 marks] Give a big-O estimate for the number of operations, where an operation is a comparison or a multiplication, used in this segment of an algorithm. Ignore comparisons used to test the conditions in the for loops (a1, a2, …, an are positive real numbers).
m := 0
for i := 1 to n
for j := i + 1 to n
m := max(ai×aj, m)
 We have two nested for loops. In the inner loop, we have one comparison. Thus, we need to find how many times the inner for loop is executed. The inner loop is executed n-i times. Therefore, total number of operations are as follows:
(n-1) + (n-2) + (n-3) + … + (2) + (1) = (n-1)(n)/2
Therefore, the number of operations of the above code is O(n2)
Note 1: Σ𝑖𝑛𝑖=1=(𝑛)(𝑛+1)/2
Note 2: the above sequence is from 1 to (n-1)
5) [10 marks] Give a big-O estimate for the number of operations, where an operation is an addition or a multiplication, used in this segment of an algorithm. Ignore comparisons used to test the conditions in the while loop.
i := 1
t := 0
while i ≤ n
t := t + i
i := 2×i
We have two operations (constant number of operations) inside the while loop. Thus, we need to find how many times while loop is executed. In every iteration of the above while loop, the value of i is doubled. For example, if n is set to 2k, after k operations, i would be equal to 2k which is the value of n. Therefore, the while loop is executed k times, which is equal to log2(n). (Note: n = 2k ⟹ k = log2(n) ) Therefore, the number of operations of the above code is O(log2(n))
6) [6 marks] Suppose that an element is known to be among the first four elements in a sorted list of 64 elements. Would a linear search or a binary search locate this element more rapidly? Justify your answer.
A linear search is faster. Because linear search will find the element in at most 4 steps. However, binary search needs to check lists with the following sizes to find the element: 64, 32, 16, 8, 4, 2, 1. Therefore, the number of steps of binary search are higher than 4 steps of the linear search.