## DESIGN AND ANALYSIS OF ALGORITHM

Examples based on Asymptotic Notations
9 November, 2016

5) CONSIDER THE following C code segment . Let T(n) denotes the number of times the for loop is executed by the program on input n .

which of the following is TRUE?
int Is Prime(int n)
{

for(int i=2; i<=sqrt(n); i++)
If(n%i== 0)
{
Printf(“Not prime \n”);
return 0;
}
Return 1;
}
a)T(n)= O(n)
b)T(n)= O(√n) and Ω(1)
c) T(n)= O(n^2)
d)None of these

Ans: As you can see this for loop run maximum for sqrt n and minimum for 1

6) In the following C function, let n>=m . How many recursive calls are made by this function?

int gcd(n,m)   {
If(n%m ==0) return m;
n=n%m;
Return gcd(m,n);
}

a)O(n)
b)O(n!)
c) O(logn)
d)None
Ans : All are incorrect. Running time is O(1).

9) Let f(n) = 3n+1 and f(n) = o g(n). then find  g(n) = ?

Sol- f(n) = 3n+1
g(n) = ?
and relation is f(n) ≤ g(n)
so g(n) must be greater
then we can say g(n) is in power of n where power > 1 like  n^2, n^3…………

10)         f(n) = { ∑_(i=1)^n▒i}  , g(n) = o(n^3)
Sol:       f(n) = n(n+1) = 0(n^2)
f(n) ≤ o g(n)

because f(n) < g(n).

11)  Find upper bound for f(n) = 3n+8?

ANS: 3n+8<=4n, for all

n>=8

Means 3n+8=O(n) according to rule
F(n) <=g(n)
With c= 4 and n0 = 8.

These are some examples based on Asymptotic Notation .

You can solve any problems regarding Time Complexity.

In the next chapter , we will study Recursion and How to solve recursion..

Till den have fun.