COMPUTER SCIENCE AND ENGINEERING
ALGORITHMS
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
Express the formula (n-1)*(n-5) in terms of big Oh notation
|
|
O(1)
|
|
|
O(log n)
|
|
|
O(n)
|
|
|
O(n2)
|
Explanation:
Detailed explanation-1: -Question 1: The correct answer is Option c. i.e O(n2). As if we expand the formula (n-1)*(n-5) = n2-n-5n + 5 = n2-6n + 5. So, its big Oh notation will be O(n2).
Detailed explanation-2: -Big-O means “is of the same order as”. The corresponding little-o means “is ul-timately smaller than”: f (n) = o(1) means that f (n)/c !
Detailed explanation-3: -In a formal big-O proof, you first choose values for k and c, then show that 0 ≤ f(x) ≤ cg(x) for every x ≥ k. So the example from the previous section would look like: Claim 51 3x2 + 7x + 2 is O(x2). Proof: Consider c = 4 and k = 100.
There is 1 question to complete.