Author
Is Big-Oh analysis always based on the number of nested loops? For instance, if I have one loop it is O(N) and if I have 10 nested loops it is O(N^10)? Is it possible for one loop to have a worse Big-O bound than nested loops?
In the case of examining the runtime efficiency of an algorithm written in a structured programming language, examining the number of nested loops is often a good indicator of big-O performance. However, this is not always the case.
Quote:Original post by Sneftel
In the case of examining the runtime efficiency of an algorithm written in a structured programming language, examining the number of nested loops is often a good indicator of big-O performance. However, this is not always the case.
for example:
int pow(int a, int b) { int result = 1; for (int i = 0; i < b; ++i) { result *= a; for (int j = 0; j < 5; ++j) { result += 1; } result -= 5; } return result;}even though it has a nested loop [yes, a stupid nested loop] it is still run in linear time, the number of iterations in the inner loop doesn't depend on the value of b so [essentially] has no effect on the big-o
you will not always be finding the big-oh of loops like that one.
def bsearch(lst, value): low = 0 high = len(lst) while low < high -1: index = (low + high) / 2 if lst[index] == value: return index elif lst[index] > value: high = index else: low = index # not found return -1turns out that runs in log n time [its a binary search]
Quote:Original post by Gink
Is Big-Oh analysis always based on the number of nested loops? For instance, if I have one loop it is O(N) and if I have 10 nested loops it is O(N^10)? Is it possible for one loop to have a worse Big-O bound than nested loops?
Yes. Consider the following bad code for traversing a maze:
public MazeResult AwfulMazeBFS(Node startingNode){ MazeResult result = MazeResult.SolutionNotFound; // Node.Children contains the child nodes (if they exist) to the north, east, // south, and west, in that order. foreach (Node reachableChild in startingNode.Children) { if (reachableChild == NodeType.MazeExit) { result = MazeResult.Success; } else { result = AwfulMazeBFS(reachableChild); } } return result;}Suppose you start at node 5 in the diagram below:
1--2--3| | |4--5--6--X| | |7--8--9The code will visit 2 first. Having not found an exit there, it proceeds to examine 3. No exit there either. Now it examines 5 -- which it just came from -- and finds nothing. Next, 1. It winds up traversing the nodes in this order before declaring success:
5, 2, 3, 5, 1, 6, 3, X
Clearly this was wasteful -- it looked at 3 and 5 twice even though it had already visited them. So even though this was a simple loop, it did a lot of unnecessary traversals. In an infinite maze-grid, an optimal algorithm would give you O(n) search performance, but this BFS would give you O(n^2) or worse performance: you examine every node, and all that node's children, some of which may be previous nodes.
Quote:Original post by Gink
Is Big-Oh analysis always based on the number of nested loops? For instance, if I have one loop it is O(N) and if I have 10 nested loops it is O(N^10)? Is it possible for one loop to have a worse Big-O bound than nested loops?
Big-Oh notation is used to give a superior bound of the assimptotic complexity of a given function f.
In the case if you have nested loops it can happen two things....
1st - You run through all of the N elements in all of the loops (or something like that)
2nd - 1 is not always true.
In the first case w(f(N)) = t(f(N)) = O(f(N))
where w is Omega notation and t is Theta notation.
That is true because in the first case what happens is that you have a case where you always go through all the N cases, so you have a t(f(N)), and you know that w(f(N)) is a lower bound of t(f(N)), but like there's no better possible case w(f(N)) = t(f(N)). It's the same justification (worst case) for O(f(N)).
Big-Oh, therefore, is used for analyzing the assimptotic complexity in a way you can obtain a superior bound for the given function.
Omega notation is for the best case and Theta is for the average case.
Sometimes you can have various O bounds and Theta bounds... It's a question of semantics... Like this example....
If you were asked to give the O of the function f, such as f is the search function in an Binary tree you would have two cases that are "normal"...
1st - It's a wonderful binary tree that you were lucky like hell and it's perfectly balanced. If this was an AVL that would be the only case... Even when you reach the 2 level of height difference the only thing that would change would be in a constant time C1 so it wouldn't change the assimptotic funtion (I'm assuming.. I didn't analyze this... One tends to develop a kind of instinct for those things :p)
So... It's perfectly balanced... O(f(n)) would be lg N, because that's the worst case where you go in a perfect balanced tree till the last element (following the rules of a binary tree...). that's to say
Origin
/ N/2 / \ N/2
X Y
/\ / N/4 / \N/4/ \N/4
A B C D
then N/8, N/16, etc...
(Don't mind the names I give to things...)
So at each level we got N/2 of the previous level....
So if we have N elements and we go only for one place at a time, will have lg N (if we go to the end).
2nd - You would have a binary tree that would have all the nodes to the left or all the nodes to the write and searching would be O(N), because that would be the worst case (when what you are looking for is at the end...)
Then you should see also in the average case of organization of the average tree, but I think that's too much for a reply....
You should read Introduction to algorithms or The art of computer programming (and some things that concrete mathmatics has related to assimptotic functions... but i haven't read those :p)
I hope i'm not forgetting something and I hope this helps....
Quote:Original post by Gink
Is Big-Oh analysis always based on the number of nested loops?
Not the number of nested loops, but the start/end conditions of the nested loops, as shown above. Also, don't forget about recursion (although all recursions can be reduced to iteration, so I guess you can forget about recursion). ;)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
