The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+16 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.

+23 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 \\=T(1) + \frac{1}{2} + \frac{1}{3}+ \dots + \frac{1}{n} + (n-1) c \\=A(1) +\frac{1}{2} + \frac{1}{3} \dots + \frac{1}{n} + nc \\= 1 +\frac{1}{2} + \frac{1}{3} \dots + \frac{1}{n} + nc \\= \log n + nc $

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

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

$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 \\=T(1) + \frac{1}{2} + \frac{1}{3}+ \dots + \frac{1}{n} + (n-1) c \\=A(1) +\frac{1}{2} + \frac{1}{3} \dots + \frac{1}{n} + nc \\= 1 +\frac{1}{2} + \frac{1}{3} \dots + \frac{1}{n} + nc \\= \log n + nc $

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

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

@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**

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?

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?

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

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

@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

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

It will not c, c1.....

c will be same for each calling

It will not c, c1.....

c will be same for each calling

@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?

My doubt is why add the constant part in the recurance relation?

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 284
- Exam Queries 397
- Tier 1 Placement Questions 17
- Job Queries 51
- Projects 7

33,705 questions

40,252 answers

114,340 comments

38,861 users