Need an Algorithm in O(n^n)
Author
Hi there,
I wanna a sample algorithm that take O(n^n) 'Big O' for runnig time.
Is there this algorithm ?!?!?
let waste_time n = let vector = Array.make (n-1) 0 in let rec repeat z = let i = ref 0 in while i < (n-1) && vector.(i) = n do vector.(i) = 0; incr i done; if !i = (n-1) then z else (vector.(i) <- vector.(i) + 1; repeat (not z)) in repeat false;;Determines if n (n-1) is odd or even by counting up to n (n-1) one at a time. Each addition takes an average of n, which gives O(n n) time complexity.
Author
Thanks dear friend.
Can you give me more information about your algorithm ?
If possible convert this algorithm to C++ or VB language mode.
Can you give me more information about your algorithm ?
If possible convert this algorithm to C++ or VB language mode.
Isn't most of mathematically provable solutions of Hamilltonial problems a high order O algorithm?
Give him rather usefull real live situation that requires O(n^n).
Actually it might be rather easy, geometry algorithms are measured by worst case situation, and many of simpler geometry algorithms are high order.
Give him rather usefull real live situation that requires O(n^n).
Actually it might be rather easy, geometry algorithms are measured by worst case situation, and many of simpler geometry algorithms are high order.
Quote:Original post by BrianL
strlen
is O(n) for sure, for any given input it only depends on the size as the increment operation is constant time ;)
What you are looking for is an algorithm that requires to look at the whole input for any input element that is processed - and such extremly wasteful algorithms are not too common.
Quote:Original post by Raghar
Isn't most of mathematically provable solutions of Hamilltonial problems a high order O algorithm?
Give him rather usefull real live situation that requires O(n^n).
I don't really think an O(n n) complexity can qualify as useful. Besides, these are quite complex to describe.
Quote:Actually it might be rather easy, geometry algorithms are measured by worst case situation, and many of simpler geometry algorithms are high order.
I was under the impression that they are mostly quadratic or cubic in complexity, and were usuallly measured by their average complexity (including an initial randomization).
Haha, I totally misread the topic as looking for an O(n) algorithm. So sorry about that! Thats what I get for responding to a topic on my way out the door.
I don't know of any N^N algorithms off hand. Does that class even have a name? I can't think of a case where I have encountered it - if I did, it would probably still be running. ;)
I don't know of any N^N algorithms off hand. Does that class even have a name? I can't think of a case where I have encountered it - if I did, it would probably still be running. ;)
Author
No this isn't my homework!!!
(My homework is worse than it usually [lol])
I interested in this topic,because i think about this before and couldn't found a algorithm that worse than O(n!).
(My homework is worse than it usually [lol])
I interested in this topic,because i think about this before and couldn't found a algorithm that worse than O(n!).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
