190 views

What is the running time of the following loop?

Loop2(n)
p <-- 1
for i <-- 1 to 2n do
p  <-- p*i 
1. $\Theta(n^2)$
2. $\Theta(n)$
3. $\Theta(n\lg n)$
4. $\Theta(n^2\lg n)$

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).


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.