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

  • Thread starter Thread starter Jarvis323
  • Start date Start date
  • Tags Tags
    Formula
Click For Summary
SUMMARY

The discussion focuses on plotting the running time of an algorithm defined by the formula expO((log N)^α(log log N)^(1−α)) = L(a). The specific values of 'a' to be analyzed are a = 1/4 + O(1), a = 1/4 + O(n), and a = 1/3, with the expectation that their growth will be ordered from smallest to largest. The user seeks assistance in interpreting this formula for accurate plotting, referencing both the original research paper and a preprint version for further details.

PREREQUISITES
  • Understanding of algorithmic complexity and growth rates
  • Familiarity with logarithmic functions and their properties
  • Experience with plotting functions using tools like Python's Matplotlib or R
  • Knowledge of asymptotic notation, specifically Big O notation
NEXT STEPS
  • Research how to implement logarithmic functions in Python using NumPy
  • Learn to use Matplotlib for visualizing mathematical functions
  • Explore asymptotic analysis techniques for comparing growth rates
  • Study the implications of different values of 'a' on algorithm performance
USEFUL FOR

Researchers, data scientists, and computer scientists interested in algorithm analysis and performance visualization, particularly those working with logarithmic growth functions.

Jarvis323
Messages
1,247
Reaction score
988
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.
 
Physics news on Phys.org
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})##.
 

Similar threads

  • · Replies 9 ·
Replies
9
Views
5K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
3K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 65 ·
3
Replies
65
Views
9K
  • · Replies 1 ·
Replies
1
Views
4K
Replies
1
Views
2K
Replies
2
Views
2K
  • · Replies 7 ·
Replies
7
Views
3K