1

I recently took an algorithms and data structures exam. One of the questions was to create a list of steps and flowchart for an algorithm that calculates the roots of a quadratic equation. I was also tasked to provide the Big O complexity of the provided algorithm.

Basically, my algorithm was like the one presented here :

Step 1. Start
Step 2. Read the coefficients of the equation, a, b and c from the user.
Step 3. Calculate discriminant = (b * b) – (4 * a * c)
Step 4. If discriminant > 0: 
    4.1: Calculate root1 = ( -b + sqrt(discriminant)) / (2 * a)
    4.2: Calculate root2 = ( -b - sqrt(discriminant)) / (2 * a)
    4.3: Display “Roots are real and different”
    4.4: Display root1 and root2
Step 5: Else if discriminant = 0:
    5.1: Calculate root1 = -b / (2 *a)
    5.2: root2 = root1
    5.3: Display “Root are real and equal” 
    5.4: Display root1 and root2
Step 6. Else:
    6.1: Calculate real = -b / (2 * a)
    6.2:Calculate imaginary = sqrt(-discriminant) / (2 * a)
    6.3: Display “Roots are imaginary” 
    6.4: Display real, “±” , imaginary, “i”
Step 7. Stop

As an answer to the question of complexity, I submitted O(1) because there is always a constant amount of steps required to find the roots. However, Professor provided me with feedback that the answer is incorrect without providing the correct one.

I couldn't find any answers to this question so I require help. What is the complexity of such an algorithm?

Spektre
  • 49,595
  • 11
  • 110
  • 380
Kielx
  • 19
  • 1
  • 2
  • 1
    That approach is O(1), but there are iterative methods for approximating the root values. Maybe prof expects you to evaluate a different algorithm? – danh Jun 22 '21 at 15:14
  • Probably best to ask your professor because that looks like O(1) to me as well – SirGuy Jun 22 '21 at 15:16

2 Answers2

1

The time complexity of our algorithm should be log(n), that is because for most of the square root(taking square roots) are log(n). So time complexity some be log(n)

Where n is the number that you are taking suqare root

lier wu
  • 620
  • 7
  • 23
  • What's n in this case? – SirGuy Jun 22 '21 at 15:16
  • 1
    Except that it isn't: https://stackoverflow.com/questions/34580158/time-complexity-of-math-sqrt – RBarryYoung Jun 22 '21 at 15:25
  • @RBarryYoung But it's not, https://stackoverflow.com/questions/34580158/time-complexity-of-math-sqrt#comment119469000_34580207 – lier wu Jun 22 '21 at 15:29
  • 1
    Actually I am not sure, I might just delete this answer – lier wu Jun 22 '21 at 15:29
  • 1
    I wouldn't delete it. You are probably right in the sense that this is probably what the professor of the class was thinking. – RBarryYoung Jun 22 '21 at 15:31
  • But was he correct then? Is it O(1) or log(n)? – Kielx Jun 22 '21 at 15:33
  • 1
    Disagree with @RBarryYoung that this is the pedagogical intent unless it's a class whose subject is the nuance of math function implementations in commercial systems. If the class is about algorithms, and the question is about quadratics, I think the right assumption for sqrt() is O(1) – danh Jun 22 '21 at 15:36
  • @danh The professor had *some* reason for saying that O(1) was wrong. What other reason would make more sense? I have certainly known professors who would say that on the basis of the theoretical algorithmic principles of any square root algorithm, irrespective of how they are implemented in commercial systems (where they are actually O(1), not the other way around). – RBarryYoung Jun 22 '21 at 15:44
  • @RBarryYoung, I suggested to the OP that the prof’s intent might be to explore iterative approaches to root approximation. I think that’s a more plausible intent. (Interesting complexity questions, there, related to the order of the polynomial, desired accuracy, rate of convergence, etc). Not that sqrt might not be interesting, too, just less likely I think. – danh Jun 22 '21 at 15:54
  • @danh It doesn't make sense to mark a student wrong for analyzing the correct algorithm correctly. It only makes sense if the professors interpretation of one of the constituent steps is different from what the student assumed. – RBarryYoung Jun 22 '21 at 16:10
  • I do not think this is the case... sqrt is `O(log(n))` only if it is implemented in SW which is nowhere mentioned, if it uses bignumber it would be much worse than just `O(log(n))` too I think you all are missing the point and focusing on the equation while the problem is most likely in not accounting for input and output of the algorithm – Spektre Jun 23 '21 at 07:41
  • @Kielx It depends if it is implemented in software or hardware. In SW it would follow the standard rules of complexity analysis and would probably be `O(log n)` (depending on the specific algorithm used). HW however can implement any level of word-length bit-parallel circuitry that it chooses to reducing almost any single HW instruction to effectively O(1). Since there are FSQRT machine instructions, from a practical standpoint, SQRT is an `O(1)` operation. – RBarryYoung Jun 23 '21 at 14:47
1

The computation itself on CPU/FPU native datatype is O(1) however if big numbers are involved then its no longer the case as most arithmetic operations are no longer O(1) and vary on implementation for example +,- are O(n) and multiplication is O(n^2) or "slightly" faster depending on algorithm used where n is number of bits used. However I doubt this is the case.

As your algorithm contains more things then just computation of the equation You need to account for that too which is most likely the discrepancy your lecturer had in mind.

You know getting input from user is not O(1) nor is converting string to number ... The same goes for printing (converting number to text, and print strings)

So I would bet the correct answer should be O(n) where n is max (or sum) number of digits/characters your code uses for input and output ... Again if big numbers are involved it will be much worse unless you are printing in numeric system that is compatible with number representation...

So you have to account step #2 and each Display...

Spektre
  • 49,595
  • 11
  • 110
  • 380
  • Correct me if I'm wrong, but I understand that You are implying that the complexity of the proposed algorithm is 0(n) based on the number of digits and characters in input and output? You also mention that O(1) is wrong in this case because the algorithm needs input from the user and accepting input is not O(1). Wouldn't that mean that there are no algorithms that are O(1)? Because the complexity of any algorithm could be manipulated and changed only because of the way the input is provided? – Kielx Jun 23 '21 at 14:55
  • If as you suggest the answer is O(n) would the number of steps be different if I provide a number like 10, 100, 1000, or 500000? If O(n) is the case it should be, right? Also, would sorting algorithm complexity change only because of the way the input is provided? If I provide the input from the user would it be O(n) for sorting array of 10 elements? And if I provide it by other means would it be O(1)? Shouldn't we consider just the base algorithm and not the ways the input is provided? – Kielx Jun 23 '21 at 14:56
  • @Kielx basically complexity is analogy to number of cycles or steps to complete program (without the constant time) so in your case the computation itself is `O(1)` however program that reads the input has cycles (loops in it) for example when you type `12345` you need to iterate the keyboard handling and string appending 5+1 times ... and as its depended on the input size its not constant hence `O(n)` where `n` is number of inputed characters ... for numbers `n = log10(number)` and its the same as bitwidth (just different log base)... While printing strings and numbers its the same ... – Spektre Jun 23 '21 at 15:21
  • Even if you do this with just single function call there are loops behind it inside its implementation... hence printing 10 characters is faster than printing 1000 characters ... – Spektre Jun 23 '21 at 15:24
  • I understand then, that if I were to remove step 2 and provide the data for the algorithm as a parameter for a function, the complexity would be O(1)? – Kielx Jun 23 '21 at 15:25
  • @Kielx yes if you hard code the input and remove the display ... There is also another hack ... if your input/output will be always constant size then it is considered `O(1)` ... so for example if you input always 4 digit numbers its `O(1)` ... because 1234 will take the same time/steps/cycle as 0001 regardles of the input value. The same goes for printing – Spektre Jun 23 '21 at 15:35