+1+1+1+1 n(2+3+4+4) +1+1 n(2+3+1+4) +1+1 idk how the while loop works
5 Matching Annotations
- Jan 2025
-
runestone.academy runestone.academy
-
-
T(n)=2n+26 steps.
How?
-
-
runestone.academy runestone.academy
-
The first term is the constant 3, representing the three assignment statements at the start of the fragment. The second term is 3n2, since there are three statements that are performed n2 times due to the nested iteration. The third term is 2n, two statements iterated n times. Finally, the fourth term is the constant 1, representing the final assignment statement. This gives us T(n)=3+3n2+2n+1=3n2+2n+4. By looking at the exponents, we can easily see that the n2 term will be dominant and therefore this fragment of code is O(n2).
how to get the T(n) equation
-
Name
table top to bottom fast to slow. factorial is slower than exponential.
-
s O(n2).
As n becomes larger the most dominant part of the equation becomes n^2 so its O(n^2).
-