1.3k views

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

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

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
+5

@Srestha, Could you pls help why have we added constant 'c' in the recurrence? The question does not mention that on its own isnt it? I can understand that decrement of (n-1) or call function might take some constant time but shouldnt we follow the question exactly in such cases?
I mean to say the reccurrence should be

T(n) = T(n-1) + 1/n

T(1) = 1

Solving we get log n

0
See here procedure A and procedure B takes O(1) and O(1/n) time.

But other than this what() is also doing it's work in some constant time.

It will call upto n times. So O(nc)

right?
+1

@Srestha Yes I understood that point. But my doubt is - Is it fair to assume that? In ideal case yes the operation what call() is going to take some constant time. But nothing is mentioned in question explicitly about that.

Usually in such questions they include this line - "All the other operations take constant amount of time" which is missing here.

+2

" time complexity of the algorithm ".

not the time complexity of A,B

So, u have to think about complexity of whole algo

+1

@srestha,@arjun sir

$Point1$

If i consider merge sort recreance

$T(n) = 2T(n/2) +0(n) +c$

Each call to merge will solve two subproblems,and then we have $(o(n)$ time to merge them by a fxn call.Now it will also do some constant operations which are represented by $c$.

But we take $n+c=n$ and write it as :-

$T(n) = 2T(n/2) +0(n)$

so, why cant i remove c here as @yg92  has aksed?

--------------------------------------------------------------------------------------------------------------------------

$Point2$

If i cannot be done then i think we can rewrite the given recreance as:-

$T(n)=T(n−1)+1/n+c$

$T(n)=T(n−1)+c1+c$// As 1/n is always less than 1,means some constant(c1)

$T(n)=T(n−1)+k;$// k is a constant ,k=c1+c

Now solve it we get $o(n)$ times.Please check once,?

But we cannot remove c,as i did in point 1,because $1/n$ can be less than 1(it cannot be even equal because if 1/n=1 means n=1 means base condition),but constant will always be +ve,may be one or more,so constant will dominate.

More strongly i can say that $1/n$ is strictly less than constant

+1
when same function is called , then constant will not change rt?

It will not c, c1.....

c will be same for each calling
0
@srestha @Arjun sir I still didn't get the answer to my doubt after reading the comments as well.
My doubt is why add the constant part in the recurance relation?
0
if n = 1 then call A need one comparision in each call and
we doing constant work i.e. for call B () which took O(1) time
0
yah constant is for O(1)
0
same doubt as @yg92 :(
0
amazing arjun sir
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).