GATE CSE 1999 | Question: 11a

Question

Consider the following algorithms. Assume, procedure $A$ and procedure $B$ take $O (1)$ and $O(1/n)$ unit of time respectively. Derive the time complexity of the algorithm in $O$-notation.

algorithm what (n)      
begin 
    if n = 1 then call A 
    else 
        begin
            what (n-1);
            call B(n)
        end
end.

Comments

Procedures A() will be called 1 time, B() n-1 times and function what() will be called n times.

total T.C will be as shown below

---

This doesn't seem right  as we need to find for what itself and your declaring it as directly o(n) so there is no need to find the inner functions value if we know  the outer value

Answer 1

The recurrence relation for time complexity is

$T(n) = T(n-1) + \frac{1}{n} + c$ $(O(1/n)$ replaced with $1/n$ and so our answer will also be in $O$ only and not $\Theta)$

$T(n) = T(n-2) + \frac{1}{n-1} + \frac{1}{n} + 2c $
$\\\qquad=T(1) + \frac{1}{2} + \frac{1}{3}+ \dots + \frac{1}{n} + (n-1) c $
$\\\qquad=A(1) +\frac{1}{2} + \frac{1}{3} \dots + \frac{1}{n} + nc$
$ \\\qquad= 1 +\frac{1}{2} + \frac{1}{3} \ldots + \frac{1}{n} + nc$
$ \\\qquad= \log n + nc $

$($Sum of the first $n$ terms in harmonic series is $\Theta(\log n))$

So, our time complexity will be $O(n)$.

Comments

@MRINMOY_HALDER

Time complexity means maximum time it could take to solve a equation. right?

And though recurrence term growing slowly, but constant term growing faster.

---

@sreshta mam

can u please explain little more

---

but why we are considering O(1/n) part every time to calculate complexity ..it will only used when n = 1 ?

Answer 2

Actually, The number of operations required to call what(n-1) like pushing the activation records onto the stack etc overshadow the time taken for B(n) when we are talking in asymptotic world. So, the recurrence relation will be

T(n) = T(n-1) + O(1), solving this, we get

 

T(n) = O(n).

Answer 3

We don’t need to do recurrence relation at all for this, A is O(1), B is also O(1) because take 1/n, lets assume n is not zero, then for any value of n, 1/n is going to be less than 1 so it is actually O(1) or less. So we can just ignore the call for A and B from the algorithm. So what(n) is called recursively till it reaches n = 1, so it is called n times. So the answer is, O(N).