1
$\begingroup$

I am sorry if these are such stupid noob questions. I am just getting into CS.

I read a passage in a book that says:

Time complexity is written T(n). It gives the number of operations the algorithm performs when processing an input of size n. We also refer to an algorithm’s T(n) as its running cost. If our code follows T(n) = n2, we can predict how much longer it takes to sort a deck once we double its size:

enter image description here

Questions:

  1. Firstly, why does our code follow T(n) = n2 ? I don't get why we make that assumption
  2. I do not understand what this means, n2 means squared, correct? so if n is 8 then it's: T(8) = 64, right?
  3. Next we have the T(2n)/T(n) = 4, lets say n is 2 then its T(4)/T(2) = 2, right?

Again I am a noob so please be gently and I would really appreciate detailed answers. Thank you

$\endgroup$
1
  • 3
    $\begingroup$ You are happy with T(8) = 64. So you should be happy with T(4) = 16 and T(2) = 4. Then T(4)/T(2) = 16/4 = 4, not 2. $\endgroup$ Jun 26 '21 at 16:06
5
$\begingroup$
  1. This is just an example. Easiest to think of an algorithm that has two nested loops over an array of size $n$ (e.g. Bubble Sort).

  2. You are correct. Again, if you think of an algorithm that has two nested loops and within the inner loop just one (or constantly many) operation $op$, then $op$ gets executed $n^2$ times. If you array has size 8, $op$ gets executed 64 times.

  3. No, the ratio is constantly 4. $\frac{T(2n)}{T(n)} = \frac{(2n)^2}{n^2} = 4$. The intuition here is that quadratic runtime means: By $k$-folding the input size, the runtime gets $k^2$-folded.

$\endgroup$
0
$\begingroup$

It means we try to express the time needed to solve a problem as a function of the problem size, so that we know how to deal with larger problem sizes & scalability issues

  • For example if we find it is linear in the problem size (T(n)=an+b) that's probably cool, if n=1000 or even n=10⁹ we can manage (our program will end its run in a acceptable time)

  • While if we calculate it to be exponential in n (T(n)= a•2^n), that could cause a scalability problem; if n=10 that's 1024a, but what if n=100? 2¹⁰⁰ is an infinite time, we have to think of another way (algorithm) to solve the problem

That's the explaining, as for ur example

If T(n)=n², then

T(2n)=(2n)²=2²•n²=4•n²= 4•T(n)

If n=2, T(n)=4, T(2n)=4²=16 If n=8, T(n)=64, T(2n)=16²=256 =16•16=4•4•16=4•64

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.