6,411 views
41 votes
41 votes

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.

3 Answers

Best answer
54 votes
54 votes
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)$.
edited by
4 votes
4 votes
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).
0 votes
0 votes

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).

Related questions

30 votes
30 votes
5 answers
1
Kathleen asked Sep 23, 2014
9,015 views
If $n$ is a power of $2$, then the minimum number of multiplications needed to compute $a^n$ is$\log_2 n$$\sqrt n$$n-1$$n$
57 votes
57 votes
6 answers
2
Kathleen asked Sep 23, 2014
19,624 views
Suppose we want to arrange the $n$ numbers stored in any array such that all negative values occur before all positive ones. Minimum number of exchanges required in the w...
31 votes
31 votes
3 answers
3
Kathleen asked Sep 23, 2014
5,076 views
Let $A$ be an $n \times n$ matrix such that the elements in each row and each column are arranged in ascending order. Draw a decision tree, which finds $1$st, $2$nd and $...