Member Avatar for 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?

  • 3 Contributors
  • 5 Replies
  • 142 Views
  • 4 Days Discussion Span
  • Latest Post Latest Post by amina.bm
Member Avatar for 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.

Member Avatar for 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?

Edited by inspire_all
Member Avatar for deceptikon

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

Member Avatar for inspire_all

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

Edited by inspire_all
Member Avatar for 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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.