How to calculate the complexity of algorithm?

Question

Complexity Analysis Problem

I'm currently taking a intro to algorithms course and I need help solving this problem. Shown above since I'm skeptical and not so sure. :) I have two questions:

Question 1: From what I understood from my algorithms book, I believe the runtime complexity of this problem is f(n) = 3n. Why? Well because the while loop will continue to run n times and for each iteration of the loop you have 3 operations ( 1 subtraction, 1 multiplication, and 1 addition) Is my though process correct or wrong? Should it really be f(n) = 5n because of the assignment statements. I know both are the same complexity, but I'd really like to make sure explicitly.

Question 2: As for showing if the algorithm finds the value of the polynomial, is sufficient enough for me to just give an example of it finding the value of a particular polynomial say 3n^2 + 2n + 1 to prove the algorithm works or is there a better way to do so.

• arunmoezhi: you dont have to care about constants when computing time complexity. O(n) is the same as O(2n) and O(200n)
• TwilightSparkleTheGeek: Oh, okay. So is the code above complexity BigOh(n). Is my thought process right, or is the complexity something else? arunmoezhi
• arunmoezhi: You should be asking yourself these questions. how many times does the while loop run? Is the value of i independent of the work done inside the loop (other than i=i-1)?
• TwilightSparkleTheGeek: Oh, looks like a_i is dependent on i.
• arunmoezhi: yes. But a_i doesn't affect the number of times the while loop is executed. So it is safe to assume that the while loop will run for n times giving you O(n). You don't have to bother counting the number of additions and multiplications. That will change only the constants.

Answer 1

For the first question, the complexity is indeed O(n).

If you want to determine more precisely like you seem to be asking for, during every loop, your algorithm will require a certain amount of operation (my complexity lessons being a bit old, I hope I don't miss any ;)):

1. Analyzing the loop condition : i>=0
2. Calculate the product of x and y
3. Add the result to a[i]
4. Store the result in y
5. Calculate i - 1
6. Store the result in i

Your program will also do 3 extra operations :

1. y = 0
2. i = n
3. Compare i to 0 the last time, without entering the loop

You could also consider the fact the computer has to allocate memory to y and i, etc.

For the second question, as in mathematics, proving it works in one situation is not enough to prove it works in any.

To prove your algorithm, you first have to write your precondition (what you are supposed to have in entry). Then you have to indicate the status your program shall be in at the beginning of your while loop, and same at the end of it.

For example: y=0 i=n while(i>=0){ // y=Sum(a[j] + x^j, j>i) y=a[i] + x ^ i // I suppose it is meant to be x^i instead of x*y y=Sum(a[j] + x^j, j>i-1) i=i-1 // y=Sum(a[j] + x^j, j>i) }

I didn't find any necessary precondition for the program, I just mentioned it earlier because it is important to think about it for other similar works. As shown, the idea is to show the state of the program at each point, so we know the state it is in when it reaches the end.

• TwilightSparkleTheGeek: Hmm, but wouldn't that mean pick a particular polynomial still if I just state the status of my program at the beginning and end of my while loop? I mean don't I have to give a particular polynomial to work on? How do I prove it works for all polynomials in general.
• Mitvailer: You have to prove it works for all the possible entries respecting your preconditions, so in this case, for all polynomials. It is like demonstrating a rule in Maths. If you prove it works for one polynomial, it does not prove it works for all. So you have to stay generic, and as in maths, it is what makes the exercice of proving an algorithm more difficult ^^
• TwilightSparkleTheGeek: ahhh, oh boy. So it's alright for me to feel overwhelmed a bit Mitvailer? haha. Because right now I'm a little bit overwhelmed. I'm reading some math books on proofs because this is pretty new to me. I'll try and stay generic, thanks. :) And my professor is not so helpful, I'm an undergrad in CS.