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
Option (b) is correct answer.
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.
