Algorithm basics

[inspire_all]

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

[deceptikon]

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.

[inspire_all]

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

[deceptikon]

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

[inspire_all]

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

[amina.bm]

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.