Use the definition of big Oh to prove that is O(n). 2. (3 marks) Let f(n)...

  

Transcribed Image Text:

Use the definition of "big Oh" to prove that is O(n). 2. (3 marks) Let f(n) and g(n) be positive functions such that f(n) is O(g(n)). Use the definition of "big Oh" to prove that f(n) × g(n) is O(g² (n)), where g² (n) = g(n) × g(n). 3. (3 marks) Use the definition of "big Oh" to prove that n³ +n is not O(n³). 4. (6 marks) Consider the following algorithm for the search problem. Algorithm search (L, n, x) Input: Array L storing n ≥ 1 integer values and value x > 0. Out: Position of x in L, if x is in L, or -1 if x is not in L i← 0 while (i <n) and (L[i] = -1) do ii+1 if in then return -1 else if L[i] = x then return i else { } L[i] -1 return search (L,n,x) Activate Window Go to Settings to activ Use the definition of "big Oh" to prove that is O(n). 2. (3 marks) Let f(n) and g(n) be positive functions such that f(n) is O(g(n)). Use the definition of "big Oh" to prove that f(n) × g(n) is O(g² (n)), where g² (n) = g(n) × g(n). 3. (3 marks) Use the definition of "big Oh" to prove that n³ +n is not O(n³). 4. (6 marks) Consider the following algorithm for the search problem. Algorithm search (L, n, x) Input: Array L storing n ≥ 1 integer values and value x > 0. Out: Position of x in L, if x is in L, or -1 if x is not in L i← 0 while (i <n) and (L[i] = -1) do ii+1 if in then return -1 else if L[i] = x then return i else { } L[i] -1 return search (L,n,x) Activate Window Go to Settings to activ

Answer rating: 100% (QA)

Definition of BigO A function fn is said to be Ogn if there exist positive constants c and k such th... View the full answer