3
$\begingroup$

I am just looking for basic step by step in how to turn a pseudo code algorithm into a function and then how to calculate and show T(n) ∈ O(f(n)), and that T(n)∈ Sigma(f(n))

Also if someone could really explain to me in plain engish, that would be great. I'm not so good at understanding the meaning of some symbols. T(n) ∈ O(f(n)) iff ∃ c > 0, n0 > 0 such that T(n) ≤ cf (n) for n > n0

example pseudo code:

sum = 0; for(int i=0; i < N ;i++)   for(int j=0; j < i*i ;j++)     for(int k=0; k < j ;k++)      sum++; 

please don't just write the answer to it. I already know that the answer is T(n)∈ O(n^5), but I need to know how to get that answer.

2 Answers 2