Big-Theta - asymptotic bound - is solution sufficient enough?

82 Views Asked by At

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$