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.
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://www.daniweb.com/programming/computer-science/threads/467341/algorithm-basics", "fetch_time": 1537943271000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2018-39/segments/1537267163704.93/warc/CC-MAIN-20180926061824-20180926082224-00305.warc.gz", "warc_record_offset": 703013447, "warc_record_length": 12047, "token_count": 412, "char_count": 1573, "score": 3.53125, "int_score": 4, "crawl": "CC-MAIN-2018-39", "snapshot_type": "latest", "language": "en", "language_score": 0.9125463366508484, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00042-of-00064.parquet"}