How can I plot this algorithm's running time using different values of a?

  • Thread starter Jarvis323
  • Start date
  • Tags
    Formula
In summary, the conversation discusses a research paper that presents a formula for the running time of an algorithm. The formula is represented as expO((log N)^α(log log N)^(1−α)) = L(a) and is found in the introduction of the article. The individual would like to plot this function alongside another, with the growth parameterized by a= 1/4 + O(1), a = 1/4 + O(n), and a= 1/3 in ascending order. To interpret the formula and plot it correctly, the individual suggests using ##x= \log N## and ##y=\log\log N## as variables, with the argument of the exponent being ##O(x^\alpha
  • #1
Jarvis323
1,243
986
I'm studying a research paper that gives this formula for the running time of an algorithm,

expO((log N)^α(log log N)^(1−α)) = L(a)

I would like to plot this function alongside another, for a = 1/4 + O(1), a = 1/4 + O(n), and a= 1/3. The function's growth parameratized by those a's, should be ordered from small to big in the order I listed them.

Here is a link to the article, the formula is found in the introduction.
http://link.springer.com/chapter/10.1007/978-3-642-55220-5_1

If you can help me interpret this in a way that I can plot the function correctly, that would be helpful.
 
Mathematics news on Phys.org
  • #2
The preprint (free) version of the article is http://arxiv.org/abs/1306.4244. Let ##x= \log N## and ##y=\log\log N##. I parse that the argument of the exponent is ##O(x^\alpha y^{1-\alpha})##.
 

Related to How can I plot this algorithm's running time using different values of a?

1. How do I identify the variables in the formula?

In order to parse a formula, you first need to identify all the variables present. Look for letters or symbols that represent unknown values, such as x, y, or θ. They are typically located on the left side of an equal sign.

2. What is the order of operations for parsing a formula?

The order of operations for parsing a formula follows the acronym PEMDAS, which stands for Parentheses, Exponents, Multiplication and Division (from left to right), and Addition and Subtraction (from left to right). This means you should first simplify any expressions within parentheses, then solve for any exponents, and continue in that order until you have a final answer.

3. How do I handle coefficients and subscripts in a formula?

Coefficients, or numbers that are multiplied by a variable, can be treated the same as regular numbers. Simply multiply them with the rest of the expression. Subscripts, or small numbers or letters written below or beside a variable, are used to distinguish between multiple variables of the same type. Make sure to keep track of them and their corresponding variables when parsing a formula.

4. Can I use a calculator to parse a formula?

While a calculator can be helpful in solving complex equations, it is important to understand the steps involved in parsing a formula manually. This will not only improve your understanding of the formula, but also help you catch any mistakes made by the calculator.

5. How do I check if my parsed formula is correct?

One way to check if your parsed formula is correct is to plug in values for the variables and see if the result matches the original formula. Another method is to use a graphing calculator to plot the original formula and the parsed formula, and see if they produce the same graph. Additionally, you can use online formula parsing tools or consult with a colleague or mentor for validation.

Similar threads

Back
Top