a) Define big O notations.
b) \( {T(n) = 4n^{2}+3n \log_{}{n} } \), express T( n ) in Big( O ) notations.
a) Let us two function f(n) and g(n). here g(n) is upper bounded of f(n) for some constant multiplier. So we can say that f (n) is of O(g(n)).
\( {f(n)<=c \times g(n) for all n>=n_{0}.}\)
f(n) and g(n) are function over non negative integer.
b) let \( { f(n) = 4n^{2}+ 3n log_{}{n} } \)
when \( {n>=1, 4n^{2}+ 3n log_{}{n} <= 4n^{2} }\)
thus \( {f(n)<=4n^{2}} \)
by definition \( {0<=f(n)<=C\times g(n)}\)
So,\( { c=4,g(n)=n^{2}}\) and \({n_{0}=1}\)
So, \( {T(n)=O(n2 )}\) for all \({n>=1 }\)
"
"Write an algorithm to test whether a given binary tree is a binary search tree."
Write short notes on:
Write a C program to find the value of Sine(X).
Write a C program to transpose of a matrix.
