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
Write the string matching algorithm due to Knuth,Moris and Pratt. Analyze its time complexity.
Find the recurrence relation of binary search and derive the time complexity of binary search.
Define software quality. Briefly explain McCall’s quality factors.
What is a priority queue ?
Define packet switching and circuit switching. What is MANET?
What do you mean by software crisis & its solution.
Write a C program to check a year is leap year or not.
Describe Cost of Software Quality
Draw the ER diagram of a hospital and explain.
