FAQ Database Discussion Community

How can we prove that the running time bound of an algorithm is tight?

Suppose we can prove that an algorithm, invoked with an input of size n, runs in time O(f(n)). I want to prove that this running time bound is tight. Two questions: Wouldn't it suffice to give a special input and show that the running time is at least f(n)? I've...

How to get Omega(n)

I have the formula a(n) = n * a(n-1) +1 ; a(0) = 0 How can i get the Omega, Theta or O Notation from this without the Master Theorem or did anyone have a good site to understand the explanation...

What is the time complexity of the given algorthm?

x=0 for i=1 to ceiling(log(n)) for j=1 to i for k=1 to 10 x=x+1 I've included the answer I've come up with here: I think the time complexity is θ(n^2 log(n)), but I am not sure my logic is correct. I would really appreciate any help understanding how to do...

Theta Runtime of a triple loop that essentially much less than n^3

I was looking at a programming question today and I had an issues finding the theta runtime of it. Basically, within my question, I form the following loop structure: for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++) for(int k =...

What is the Difference between T(n) (reccurence relations), Big O and Big Theta

I am wondering about this for my Algorithm class. It seems to be unclear what the difference is between BigO, Big Theta, and Recurrence relations (T(n)) For example: T(n) = 4T(n/3) + O(1)