DIGIT-ARC read-only archive · snapshot: July 23, 2026

DIGIT-ARC / Software / Programming

Big O notation

6 posts · originally from https://geek.digit.in/community/threads/big-o-notation.165650/

A
amrutansu garanaik Original post #1
Nov 2, 2012 at 4:23 PM
suppose an algorithm doesn't have a O or Big-Theta notation.
Does it mean it doesn't have an upper bound?If it is so, does it mean this algorithm will take an infinite amount of time to process a large data? If an algorithm has an upper bound, does it mean it can process a profoundly large amount of data under certain time?

Please help.

P.S. If my concept is wrong, then please help me rectify it
M
miltus_31 #2
Nov 4, 2012 at 2:47 PM
First of all Big-O and Big-theta and Big-omega are just notations.
If I dont go into the mathematical details they are just used to denote upper bound, tight bound and lower bound.

suppose an algorithm doesn't have a O or Big-Theta notation.
Click to expand...
This is not clear.
AFAIK upper bound of running time is denoted by the Big-O notation.

If you say an algorithm does not have an upper bound in running time, then I think the algorithm is not bound to terminate. Which is obviuosly bad.
nbaztec
nbaztec #3
Nov 6, 2012 at 8:23 PM
amrutansu garanaik said:
suppose an algorithm doesn't have a O or Big-Theta notation.
Does it mean it doesn't have an upper bound?If it is so, does it mean this algorithm will take an infinite amount of time to process a large data? If an algorithm has an upper bound, does it mean it can process a profoundly large amount of data under certain time?

Please help.

P.S. If my concept is wrong, then please help me rectify it
Click to expand...

You are correct, for an algorithm to not have a Big-Oh() or Theta(), it should be monotonically increasing in size n, i.e. not have an upper bound.
M
miltus_31 #4
Nov 7, 2012 at 11:49 AM
nbaztec said:
You are correct, for an algorithm to not have a Big-Oh() or Theta(), it should be monotonically increasing in size n, i.e. not have an upper bound.
Click to expand...
Can you please explain what is meant by an algorithm to not have Big-O or Big-Theta? preferably with example.
T
thinkjamil #5
Nov 18, 2012 at 10:51 AM
Big Oh refers to the time complexity of worst possible case with the algorithm. Every algorithm has a Big Oh , if not find it form time complexity calculations, If its still undetermined, consider it infinite. . .Think of it to hang/crash when subjected to worst input case.
@
@vi #6
Dec 10, 2012 at 10:24 PM
thinkjamil said:
Big Oh refers to the time complexity of worst possible case with the algorithm. Every algorithm has a Big Oh , if not find it form time complexity calculations, If its still undetermined, consider it infinite. . .Think of it to hang/crash when subjected to worst input case.
Click to expand...
how the case of hang/crash arises since we only consider mathematical model ?