I am wondering is my solution sufficient enough (or detailed enough) for the following question? or it is even a valid solution?
Question: Find a tight asymptotic bound ($\Theta$) in terms of the following code segment, where $n \ge 1$ is an integer. Give details of your analysis.
for i=1 to n do {
for j=1 to i do {
print("Hello")
}
}
Answer: Lets analyse what will be printed on console as n$ \to \infty $ on each iteration of outer-loop:
i=1 i=2 i=3 ... i=n
"Hello" "Hello" "Hello" "Hello"
"Hello" "Hello" "Hello"
"Hello" "Hello"
...
"Hello"
Now, lets use each printed "Hello" as a step and count total steps:
$1+2+3+...+n = \frac{n.(n+1)}{2}$
Thus:
- Worst case is: $\mathcal{O}(\frac{n.(n+1)}{2}) = n^2$
- Best case is: $\Omega(\frac{n.(n+1)}{2}) = n^2$
Therefore:
- $\mathcal{O}(\frac{n.(n+1)}{2}) = \Omega(\frac{n.(n+1)}{2}) = \Theta(\frac{n.(n+1)}{2}) = n^2$
We can also verify our answer:
$\large \lim_{n \to \infty} \frac{n^2}{\frac{n.(n+1)}{2}} = 2$ , and according to definition of tight bound: $0 < 2 < \infty$