Recently I dealt a question which is as follows
{$\ldots$ $$partialSum += i* i*i $$ # time complexity is 4n. }
How can we get this and why is the time complexity not $n+n^3$. We should get $n$ for the sum operator and $n^3$ for the triple product. What is it that I am missing?
Assuming that $n$ is the number of iterations of the loop (which you did nowhere state), every iteration does two multiplies and one add. Tha makes a total of $3n$ arithmetic operations (to which you should add loop overhead).
The is no reason that $n^3$ appears, computing $i^3$ does not count for $n^3$.
The answer $4n$ is correct if we count arithmetic operations and don't count comparisons. I assume that multiplications and additions are counted as basic operations with complexity $1$. This is an abstraction and is not indicative of how fast simple loops like this would be executed on a modern hardware after compilation using a modern compiler.
To execute the statement partialSum += i * i * i we need to perform $3$ basic operations:
i by iipartialSumAnother operations that needs to happen at every iteration, which you have omitted, are the increment/decrement of the loop counter and the check for the end of the loop. So I only get $4$ operations per iteration if I count the increment and not count the comparison, or assume that they are done simultaneously. In total this gives $4n$, where $n$ is the number of iterations.
