Suppose i have an algorithm whose time is represented by th function T(n)=n^3+2n^2
So what does n mean?

3
Contributors
5
Replies
34
Views
4 Years
Discussion Span
Last Post by amina.bm

`n` is typically represented as a collection of items being processed by the algorithm because that's easy to visualize. For example, if you have an array of 10 items, replace `n` with 10 for a specific calculation.

Ok so that's the input instance size.I also have one more doubt.How can i write a** recursive formula** for any code?

Edited by inspire_all

I'm not sure I understand the question. Can you rephrase it?

How can i write a recursive formula for a code and then solve it by substitution/master method ?

Edited by inspire_all

Greetings,

To be able to use Master Theorem, one has to check first that the initial problem satisfying the following condition:

Given problem p of size n, it may be divided into m sub-problems of equal size; inferior strictly to n, such that m>=1.

If so, p can be stated as follows:

p(n)= a p(n/b)+cn^k. k>=0, n>=1, c>=1, b>=1 such that,

a: the number of sub-problems.

n/b: sub-problems size.

cn^k: the cost of dividing p and combining then the sub-problems set.

and we have then three cases:

1. a>b^k so p belongs to O(n^(log_b(a)).

2. a=b^k so p belongs to O(n^klog(n)).

3. a<b^k so p belongs to O(n^k).

Regards.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.