1) Base of hexadecimal number system? Answer : 16 2) Universal gate in digital logic? Answer : NAND 3) Memory type that is non-volatile? Answer : ROM 4) Basic building block of digital circuits? Answer : Gate 5) Device used for data storage in sequential circuits? Answer : Flip-flop 6) Architecture with shared memory for instructions and data? Answer : von Neumann 7) The smallest unit of data in computing? Answer : Bit 8) Unit that performs arithmetic operations in a CPU? Answer : ALU 9) Memory faster than main memory but smaller in size? Answer : Cache 10) System cycle that includes fetch, decode, and execute? Answer : Instruction 11) Type of circuit where output depends on present input only? Answer : Combinational 12) The binary equivalent of decimal 10? Answer : 1010 13) Memory used for high-speed temporary storage in a CPU? Answer : Register 14) Method of representing negative numbers in binary? Answer : Two's complement 15) Gate that inverts its input signal? Answer : NOT 16)
OMEGA NOTATION (Ω)
The Omega notation provides a tight lower bound for f(n). This means that the function can never do better than the specified value but it may do worse.
Ω notation is simply written as, f(n) ∈ Ω(g(n)), where n is the problem size and
Ω(g(n)) = {h(n): ∃ positive constants c > 0, n0 such that 0 ≤ cg(n) ≤ h(n), ∀ n ≥ n0}.
Hence, we can say that Ω(g(n)) comprises a set of all the functions h(n) that are greater than or equal to cg(n) for all values of n ≥ n0.
If cg(n) ≤ f(n), c > O, ∀ n ≥ nO, then f(n) ∈ Ω(g(n)) and g(n) is an asymptotically tight
lower bound for f(n).
Examples of functions in Ω(n2) include: n2, n2.9, n3+ n2, n3
Examples of functions not in Ω(n3) include: n, n2.9, n2
To summarize,
• Best case Ω describes a lower bound for all combinations of input. This implies that the function can never get any better than the specified value. For example, when sorting an array the best case is when the array is already correctly sorted.
• Worst case Ω describes a lower bound for worst case input combinations. It is possibly greater than best case. For example, when sorting an array the worst case is when the array is sorted
in reverse order.
• If we simply write Ω, it means same as best case Ω.
THETA NOTATION (Θ)
Theta notation provides an asymptotically tight bound for f(n). Θ notation is simply written as,
f(n) ∈ Θ(g(n)), where n is the problem size and Θ(g(n)) = {h(n): ∃ positive constants c1, c2, and n0
such that 0 ≤ c1g(n) ≤ h(n) ≤ c2
g(n), ∀ n ≥ n0}.
Hence, we can say that Θ(g(n)) comprises a set of all the functions h(n) that are between c1g(n)and c2g(n) for all values of n ≥ n0.
If f(n) is between c1g(n) and c2g(n), ∀ n ≥ n0,then f(n) ∈ Θ(g(n)) and g(n) is an asymptotically tight bound for f(n) and f(n) is amongst h(n) in the set.
To summarize,
• The best case in Θ notation is not used.
• Worst case Θ describes asymptotic bounds for worst case combination of input values.
• If we simply write Θ, it means same as worst case Θ.
OTHER USEFUL NOTATIONS
There are other notations like little o notation and little ω notation which have been discussed below.
Little o Notation
This notation provides a non asymptotically tight upper bound for f(n). To express a function using this notation, we write
f(n) ∈ o(g(n)) where
o(g(n)) = {h(n) : ∃ positive constants c, n0
such that for any c > 0, n0 > 0, and 0 ≤ h(n) ≤ cg(n), ∀ n ≥ n0}.
This is unlike the Big O notation where we say for some c > 0 (not any). For example, 5n3 = O(n3) is asymptotically tight upper bound but 5n2 = o(n3) is non-asymptotically tight bound for f(n).
Examples of functions in o(n3) include: n2.9, n3 / log n, 2n2
Examples of functions not in o(n3) include: 3n3, n3, n3 / 1000
Little Omega Notation (w)
This notation provides a non-asymptotically tight lower bound for f(n). It can be simply written as,f(n) ∈ ω(g(n)), whereω(g(n)) = {h(n) : ∃ positive constants c, n0 such that for any c > 0, n0 > 0, and 0 ≤ cg(n) < h(n),∀ n ≥ n0}.
This is unlike the Ω notation where we say for some c > 0 (not any). For example, 5n3 = Ω(n3) is asymptotically tight upper bound but 5n2 = ω(n3) is non-asymptotically tight bound for f(n).
Example of functions in ω(g(n)) include: n3 = ω(n2), n3.001 = ω(n3), n2
logn = ω(n2)
Example of a function not in ω(g(n)) is 5n2 ≠ ω(n2) (just as 5≠5)
An imprecise analogy between the asymptotic comparison of functions f(n) and g(n) and the relation between their values can be given as:
f(n) = Ω(g(n)) ≈ f(n) ≥ g(n) f(n) = ω(g(n)) ≈ f(n) > g(n)