GATE Overflow | Algorithms | Test 1 | Question: 11

Question

What is the running time of the following loop?
 

Loop2(n)
p <-- 1 
for i <-- 1 to 2n do 
    p  <-- p*i 

• A. $\Theta(n^2)$
• B. $\Theta(n)$
• C. $\Theta(n\lg n)$
• D. $\Theta(n^2\lg n)$

Answer 1

Loop2(n)
p <-- 1 
for i <-- 1 to 2n do 
    p  <-- p*i 

Variable used in for loop is i. variable modify after each iteration is p actually. i remain unchange. 
So for loop will run n time and complexity will be O(n).

Comments

can u show the steps of execution pls?

---

@Arjun why it is assumed here that multiplication will take constant time? In  general, do we need to consider constant TC for multiplication?, i don't think so.