The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+19 votes
1.4k 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.
asked in Algorithms by Veteran (59.7k points) | 1.4k views
+4

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

2 Answers

+26 votes
Best answer
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)$.
answered by Veteran (367k points)
edited by
+6

@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

question is about,

" time complexity of the algorithm ".

not the time complexity of A,B

So, u have to think about complexity of whole algo

+2

@srestha,@arjun sir

Please check two points:-

$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
+1
@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
0 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).
answered by (237 points)

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,200 questions
49,670 answers
163,556 comments
65,819 users