Write a short note on Asymptotic Notations.
Asymptotic notations:
Asymptotic Notations are languages that allow us to analyze an algorithm's running time by identifying its behavior as the input size for the algorithm increases. It is used to describe the asymptotic behaviour of complexities of algorithms. They are defined in terms of functions whose domain belong to natural number N. They are of three types:
The O (big oh) Notation:
The O (big-oh) is the formal method of expressing the upper bound of an algorithm's running time. It's a measure of the longest amount of time it could possibly take for the algorithm to complete. It represents the worst case time complexity of an algorithm. For non-negative functions, f(n) and g(n), if there exists an integer n0 and a constant c > 0 such that for all integers n>n0, f(n) ≤ c*g(n), then f(n) is Big O of g(n). This is denoted as "f(n) = O(g(n))".
Ω (Big-Omega) Notation:
The Ω (Big-Omega) is the formal method of expressing the lower bound of an algorithm's running time. It's a measure of the smallest amount of time it could possibly take for the algorithm to complete. It represents the best case complexity of an algorithm. For non-negative functions, f(n) and g(n), if there exists an integer n0 and a constant c > 0 such that for all integers n>n0, f(n) ≥ c*g(n), then f(n) is omega of g(n). This is denoted as "f(n) = Ω(g(n))".
Θ (Theta) Notation:
The Θ (Theta) is the formal method of expressing the tight bound of an algorithm's running time. It's a measure of the average amount of time it could possibly take for the algorithm to complete. It represents the average case complexity of an algorithm. For non-negative functions, f(n) and g(n), f(n) is theta of g(n) if and only if there exists two non negative constants c1 ,c2>0 and initial value n0 such that c1*g(n)<=f(n)<=c2*g(n for all n>=n0
Using greedy strategy, schedule the following jobs with deadline so as to maximize the profit.
Find the recurrence relation of binary search and derive the time complexity of binary search.
Write short notes on
Write a C program to convert binary to decimal using function.
Write a C program to check a year is leap year or not.
What is Resource management?
Write short notes: B tree