Title: Why this function has logarithmic time complexity (calculating the nth root of a number)?
Tags: python;c++;math;matplotlib;time-complexity
Question: Last week, I was taking a specific MOOC about Computer Science, and the prof. used an inefficient way to calculate the square root of a number (he later showed other ways as well).
Here's a function implemented in C++:
double sqrt(double num)
double eps = 0.001;
double step = 0.001;
double result = 0.0;
while (num - (result * result) &gt; eps)
result += step;
return result;
I know that the while loop will be executed (square root of num / step) times.
And I've decided to use matplotlib to draw a plot of this function growth for a range of numbers from 1 to 199 (inclusive), and here's the result:
Then, I compared it to (log(x) / step) plot, and again here's the result:
And so, I have the following questions:
Why it's logarithmic? and why this apply for any nth root of a number (using the above method) not only square root?
What with that gap between sqrt growth and log(x)?
I'm aware that there's more efficient ways to achieve the same results of square root of a number, but I need someone to shed some light on this one.
Comment: Believe it or not, your `function 'sqrt' growth` is exactly `f(x) = sqrt(x) / step` graph.

Here is the accepted answer: You are correct when you say that the loop is executed sqrt(num) times, and that makes its complexity √num. However, contrary to the later assumption, a square root isn't logarithmic: it's simply num^(1/2), which makes it polynomial in the grand scheme of things.
A clear sign and visual help is that it's not a straight line on a logarithmic plot:
The line on the left is a square root, and the line on the right is a base 10 logarithm.
The gap, obviously, is because it's not logarithmic.
Comment for this answer: I literally need some sleep. I mistook it for logarithmic.. Thanks for clearing things up.
Comment for this answer: It's ok, I need some sleep too :)


{'source': 'StackExchangeDataset', 'subset': 'stackoverflow.com', 'metadata': {'AnswerCount': 1, 'CommentCount': 1, 'ContentLicense': 'CC BY-SA 3.0', 'CreationDate': '2016:00:04/09/16', 'FavoriteCount': None, 'PostTypeId': 1, 'Tags': '<python><c++><math><matplotlib><time-complexity>', 'Title': 'Why this function has logarithmic time complexity (calculating the nth root of a number)?', 'ViewCount': 687, 'id': 36512968, 'user_AboutMe': None, 'user_AccountId': 7937545.0, 'user_DisplayName': 'Eekan', 'user_Reputation': 71.0, 'user_Views': 16.0, 'user_id': 6096253.0}}