big 0 runtimes
[145 byte] By [cabl3a] at [2007-10-1 3:39:23] 
hey whats upcould any of you all please help me by posting different big 0 runtimes for diferent alogrithmsloops, arrays etc
«« JAXB StackOverflowError by calling setValidating(true)
»» how to put the parameter with the URL string?
»» how to put the parameter with the URL string?
sorry for the repost it was an error
cabl3a at 2007-7-8 22:30:43 >
Is your google broken?
jschella at 2007-7-8 22:30:43 >
> hey whats up
> could any of you all please help me by posting
> different big 0 runtimes for diferent alogrithms
>
> loops, arrays etc
By the way you might want to read a bit on big O notation first. That way it will make more sense you see the notation for a routine.
jschella at 2007-7-8 22:30:43 >
O(1)O(lg lg n)O(lg n)O(n)O(n lg lg n)O(n lg n)O(n lg n lg lg n)O (n lg^2 n)O(n^2)etc.
YATArchivista at 2007-7-8 22:30:43 >
And don't forget:O(2^n)
dubwaia at 2007-7-8 22:30:43 >
example: bubble sort O(n?, quicksort O(n log n)
jboeinga at 2007-7-8 22:30:43 >
A(2*a) notation is better.BTW what about O(n^e)O(n^n)and O(n^n^n)and of course a favorite oneO(n^k!) assalut problem could be this way.Raghar
Lord_of_the_chaosa at 2007-7-8 22:30:43 >
> O(1)My favorite and the one that people often forget.
jschella at 2007-7-8 22:30:43 >
> > O(1)> > My favorite and the one that people often forget.I prefer O(n^0)
dubwaia at 2007-7-8 22:30:43 >
> > > O(1)> > > > My favorite and the one that people often forget.> > I prefer O(n^0)Only heretics prefer that one.
jschella at 2007-7-8 22:30:43 >
> O(n^n^n)> O(n^k!) These are equivalent.
RadcliffePikea at 2007-7-8 22:30:43 >
> > > > O(1)> > > > > > My favorite and the one that people often> forget.> > > > I prefer O(n^0)> > Only heretics prefer that one.And the real visionaries are looking at
MartinS.a at 2007-7-8 22:30:43 >
> > > > > O(1)
> > > >
> > > > My favorite and the one that people often
> > forget.
> > >
> > > I prefer O(n^0)
> >
> > Only heretics prefer that one.
>
> And the real visionaries are looking at
>
> O(n^-1)
n**-n
Adeodatusa at 2007-7-8 22:30:43 >
> > O(n^n^n)> > O(n^k!)>> These are equivalent.Could you do a proof?Just currious.Raghar
Lord_of_the_chaosa at 2007-7-8 22:30:43 >
> > > O(1)> >> > My favorite and the one that people often forget.>> I prefer O(n^0)Is it +0 or -0?Raghar
Lord_of_the_chaosa at 2007-7-20 3:02:07 >
>>> O(n^n^n)
>>> O(n^k!)
>> These are equivalent.
> Could you do a proof?
I think he was reading the second as O(n^(n!)) (and the first as O(n^(n^n))). If so, then use Stirling's approximation: lg(n!) ~= n lg n - n. lg(n^n) = n lg n. Therefore as n tends to infinity, n! / n^n tends to 1.
YATArchivista at 2007-7-20 3:02:07 >
> >>> O(n^n^n)
> >>> O(n^k!)
> >> These are equivalent.
> > Could you do a proof?
>
> I think he was reading the second as O(n^(n!)) (and
> the first as O(n^(n^n))).
Ah yes, I see. That's a 'k' in the second one. Never mind...
Of course, k may be THETA(n)... then there's the problem of grouping.
RadcliffePikea at 2007-7-20 3:02:07 >
> >>> O(n^n^n)
> >>> O(n^k!)
> >> These are equivalent.
> > Could you do a proof?
>
> I think he was reading the second as O(n^(n!)) (and
> the first as O(n^(n^n))). If so, then use Stirling's
> approximation: lg(n!) ~= n lg n - n. lg(n^n) = n lg
> n. Therefore as n tends to infinity, n! / n^n tends
> to 1.
My understanding is that to say two functions are O equivalent, there must exist a constant c, such that when c is mutiplied to one of the functions, either function can always be ontop of the other. However, if a graph is made of n! vs n^n, then there is no constant, because the grown of n^n is much faster.
Thus, O(n^(n^n)) != O(n^(n!))
However, assuming the quoted message is correct, then O(lg(n^(n^n))) == O(lg(n^(n!)))
rkippena at 2007-7-20 3:02:07 >
> My understanding is that to say two functions are O
> equivalent, there must exist a constant c, such that
> when c is mutiplied to one of the functions, either
> function can always be ontop of the other.
There are two constants. One that says n^n^n is O(n^n!) and another that says n^n! is O(n^n^n). This means they are asymptotically equivalent.
> However,
> if a graph is made of n! vs n^n, then there is no
> constant, because the grown of n^n is much faster.
No, they grow at the same rate (asymptotically). Stirling's formula roughly says that n! can be bounded above and below by n^n, with suitable multiplicative constants.
>Thus, O(n^(n^n)) != O(n^(n!))
>
> However, assuming the quoted message is correct,
> then O(lg(n^(n^n))) == O(lg(n^(n!)))
Then O(2^(lg(n^(n^n)))) == O(2^lg(n^(n!)))
andO(n^(n^n)) == O(n^(n!))
RadcliffePikea at 2007-7-20 3:02:07 >
> My understanding is that to say two functions are O equivalent, there must exist a constant c, such that when c is mutiplied to
> one of the functions, either function can always be ontop of the other.
Your understanding has a subtle flaw. f(n) = O(g(n)) <=> EXIST N, c : FORALL x > N : f(X) <= cg(X).
YATArchivista at 2007-7-20 3:02:07 >
Well that's what you get when you try to use English to explain a mathematical definition.Are you arguing that my definiton seems like f(x) < cg(x)?
rkippena at 2007-7-20 3:02:07 >
> Are you arguing that my definiton seems like f(x) < cg(x)?That was my best guess as to your meaning.
YATArchivista at 2007-7-20 3:02:07 >
Other Topics New Topic
Other Topics Hot Topic
Other Topics
All Classified
- Archived Forums
- Enterprise & Remote Computing
- Java Essentials
- Desktop
- Core
- Solaris Operating System
- Security
- Database Connectivity
- Java Mobility Forums
- Web & Directory Servers
- Development Tools
- Application & Integration Servers
- Java HotSpot Virtual Machine
- Other Topics
- E-Mail, Calendar, & Collaboration
- Developer Tools
- General
- Administration Tools
- Sun Hardware
- Storage Forums
- Java Enterprise System
- StarOffice
- Open Source Technologies
- BigAdmin
- Real-Time
- Java Coding