The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
35 views

How do I prove theta(log n)=o(log n)? [migrated]

I'm solving a question from CLRS where we need to prove that (ceil(lg lg n))! is polynomially bounded. Let g(n)=(ceil(lg lg n))! lg(g(n))=lg((ceil(lg lg n))!) =theta(ceil(lg lg n) * lg ...
1
vote
1answer
325 views

Notation for the average time complexity of an algorithm

What notation do you use for the average time complexity of an algorithm? It occurs to me that the proper way would be to use big-theta to refer to a set of results (even when a specific try may ...
12
votes
5answers
531 views

Programmaticaly finding the Landau notation (Big O or Theta notation) of an algorithm?

I'm used to search for the Landau (Big O, Theta...) notation of my algorithms by hand to make sure they are as optimized as they can be, but when the functions are getting really big and complex, it's ...
11
votes
3answers
745 views

Please explain the statement that the function an+b belongs to O(n^2) and and Θ(n)?

Let's say I have a linear function f(n)= an+b, what is the best way to prove that this function belongs to O(n2) and Θ(n)? I do not need mathematical rigor here. I need a programmers answer. Some ...
7
votes
5answers
2k views

Theta notation on constant time. Why we use the 1?

In asymptotic notation when it is stated that if the problem size is small enough (e.g. n<c for some constant c) the solution takes constant time and is writen as Theta(1). Why we write 1 inside ...
17
votes
2answers
2k views

Why is Big O taught instead of Big Theta?

Big O notation provides an upper bound to a function whereas Big Theta provides a tight bound. However I find that Big O notation is typically (and informally) taught and used when they really mean ...