Examples on Asymptotic Analysis (Case Analysis , loops analysis, asymptomatic notation) Gate exam

Page No:-4


Q1.What is time complexity of fun ()?
Int fun (int n)
{
Int count = 0:
For (int i = 0; i < n; i++)
For (int j = i; j > 0; i-
Count count+1,
Return count;
}
Solution:
The time complexity can be calculated by counting number of times the expression "count = count+1;" is executed.
The expression is executed 0 + 1+2+3 +4 +. + (n - 1) times.
Time complexity = 0+ 1+2+ 3+ . +n-1 = e(n(n - 1)/2) = O(n^2).


Q2.What is time complexity of fun ()?
Int fun (int n)
{
Int count = 0:
For (int i = n; i > 0; i/=2)
For (int j = i; j > 0; j++)
count+= 1;

Return count;
}

Solution: for  a input integer n, the innermost statement of fun() is executed following times. so time complexity
            T(n) =  n + n/2 +n/4.......+1=O(n)
The value of count is also  n + n/2 + n/4......+1

Q3.In a competition, four different functions are observed. All the functions use
a single for loop and within the for the loop, same set of statements are executed. Consider the following for loops:
A. for(i = 0; i<n; i++)   B. for(i = 0; i < n; i += 2) 
C. for(i = 1;i<n; i *=2) D. for(i = n; i> -1;i/= 2)
If n is the sithe ze of input (positive), which function is most efficient (if the task to be performed is not an issue)?

Solution:
The time complexity ofst for loop is O(n). The time complexity of second for loop (n/2), equivalent to O(n) in asymptotic analysis. The time complexity of third for loop is O(logn). The fourth for loop doesn't terminate.

Q4.Consider the following functions:
f(n) = 2^n
g(n) = n!
h(n) = n^logn
Which of the following statements about the asymptotic behavior of f(n), g{n), and h(n) is true?
(a) f(n) = O(g(n)); g(n) = O(h(n))
(b) f(n) = 𝚯(g(n); g(n) = O(h(n))
(c) gn) = Of(n); h(n) = O(f(n))
(d) h(n) = Of(n): g{n) = 𝛀f(n)

Solution: (d)

Q5Consider the following two functions. What are time complexities of the functions?
int fun1(int n)
if (n<=1) return n;
return 2*fun1(n-1);
int fun2 (int n)
if (n <= 1) return n;
return fun2(n-1) + fun2(n-1);

Solution:
Time complexity of fun 1() can be written as T(n) = T(n-1)+C which is O(n) Time complexity of fun2() can be written as T(n) = 2T(n-1)+ C which is O(2^n)

Q6.Consider the following C-program fragment in which i, j andn are integer
variables.
for (i = n, j = 0; i> 0; i = 2, j+ = i);
Let val(j) denote the value stored in the variable j after termination of the for loop. Which one of the following is true?
(a) val(j) = 𝚯(log n)  (b) val(j) = 𝚯(sqrt (n))
(C) val(j)= 𝚯(n)  (d) val(j) = 𝚯(n log n)

Solution:
Semicolon after the for loop, so there is nothing in the body. The variable j is initially O and value of j is sum of values of i. i is initialized as n and is reduced to half in each iteration.
j = n/2 + n/4 + n/8 +.. +1 = O(n)


Q7.Consider the following pseudo code. What is the total number of
multiplications to be performed?
D= 2
  for i = 1 to n do
        for j = i to n do
              for k = j + 1 to n do

                    D = Dx3
Solutions:
The statement "D = D x 33 is executed n*(n +1)* (n - 1)/6 times. Let us see how.
For i =1, the multiplication statement is executed (n-1) + (n-2) +.2+1 times.
For i= 2, the statement is executed (n -2) + (n -3) +.......... 2 +1 times
For i = n-1, the statement is executed once.
For i= n, the statement is not executed at all
So overall the statement is executed following times
[(n-1)+ (n-2)+.....2 +1] + [(n-2) + (n-3)+..2 + 1]+ ......+ 1 + 0
The above series can be written as
S = [n(n-1)/2 + (n-1)'(n -2)/2+....+1]
The sum of above series can be obtained by trick of subtraction the series from standard Series S1 =
n+(n-1)^2 +......1^2.The sum of this standard series is n'(n + 1)*(2n + 1)/6
S1 - 2S =n+ (n-1) + .. 1 = n*(n + 1)/2
2S = n*(n+1)*(2n + 1)/6-n*(n+1)/2
S = n*(n+1)*(n-1)/6

Q8.Let A[1,.... n] be an aray storing a bit (1 or 0) at each location, and f(m)
is a function whose time complexity is e(m). Consider the following program fragment written in aC like language:
counter 0;
for (i = 1: i<=n; i++)
{
if (A[] == 1)
Counter++;
else
   {
     f(counter):
     counter = 0;
   }
}
Find true statements
Solution:
a.All 1s in A[l: Time taken is e(n) as
only counter++ is executed n times.

b.All Os in A: Time taken is (n) as
f(0) is called n times each call (n).

c.Half 1s, then half Os: Time taken is e(n)
Time = n/2 + n/2 x n =𝚯(n^2) 

Q9.In the following c function, let n >=m.
int gcd(n,m) { if n%m==0) return m; n=n%m;retun gcd(m,n);}
how many recursive calls are made by this funtion?
a.𝚯(logn)                            b. 𝚯(n)
c.  𝜣(log logn)                         d. 𝚯(sqrt(n))

solution:  a.𝚯(logn)   

Q10.For the functions, lg(n) and log(8n), what is the asymptotic relationship between these functions?
Solutions
// Try your self