-fixed-

I've thrown around strings a lot longer than that before without problems.

Maybe it's not that the string is 'too long' for a function, but that it's your code in particular that's choking on the string... it would help if you showed it to us.

You'd need to provide the function so that a Big-O analysis can be done on it.

-fixed-

My point was that you'd need to provide the function. You'd have to be trained or do a bit of study to do such an analysis. Fortunately for you, I and (most likely) others have learned about such analysis, so that when you post here, you don't have to do it.

O notation (Big O, Big omega, Big theta analysis) are ways of estimating the runtime of a chunk of code. Its usually used in the context of data structures as a way to figure out the run time of a method based on how many items are in the structure. So if you have an array of n items if you wanted to look at every item it would take O(n) time. Its pretty simple once its explained to you. Every CS major at my university picks it up in their first quarter.

That being said I'm guessing that your problem resides in the way you are handling your strings rather than your run time. Unless you are performing a large number of operations based on how long your URL is I don't think its an o-notation kind of problem, but rather a syntax or design problem.

Post your code and I'm sure someone can pick out your problem.

Hmm... I only covered basic O notation in CIS. I covered O notation in greater detail in my graduate-level numerical linear algebra (using Dr. Watkins "Fundamentals of Matrix Computations"). It can be very complicated for people, especially if their background isn't that strong in mathematics. Either way, providing your code will help significantly. Don't underestimate the complexity of Big-O as it's more than just how many items are in your structure, but how your stucture processes the items in your structure. Even if there are n items, the routine can be O(e^n) or much worse.

Originally Posted by JeremyMiller

Don't underestimate the complexity of Big-O as it's more than just how many items are in your structure, but how your stucture processes the items in your structure. Even if there are n items, the routine can be O(e^n) or much worse.

Right. But in the case of performing a linear search in a set of n items using a flat data structure like an array your average case search time (in o notation) is O(n). Personally I would love to see a search algorithm poor enough to perform in O(e^n) just for fun

But to get back on topic... I'm guessing that the problem with his code has to deal with a syntax error or something like that, unless he is trying to sort to characters in the url lexographically using bubble sort

I'll have to check on the O(e^n) code. I remember crossing that once and it's probably more complicated than most here will understand -- I'll PM you when I find it, but I'm drunk tonight so O(e^n) stuff would be outside my brain's capacity right now.

If it were a syntax error that he was experiencing, then it wouldn't work for short URLs.... It will be interesting to see the function, however, as we could then discuss it's Big-O equivalence. As a bit of a side note, I see nothing in the original post which suggests a linear calculation -- am I missing something? What suggested to me that there was an issue with calculational complexity is that with a short URL (as provided) it worked in a short time but with a moderate URL (as provided) it didn't. That screams calculational complexity to me.

For those others who may be reading, not all Big-O stuff is related to one variable. Having O(m*n) is just as possible as well where m != n. There could be more than one variable affecting the overall complexity. Also, Big-O simplifies things down substantially. For example, if the calculated complexity was 3m*n^2 + 500n + 4000000, then the Big-O notation would only be O (n^2) as the other values are irrelevant as n->infinity (unless, m->infinity and n does not). [Now, I might be a bit wrong there as the alcohol has clearly set in and then the Big-O notation would be O(m*n^2) where m or n approaches infinity, but again, that depends on the nature of the issue involved.] The true key, however, is "how your stucture processes the items in your structure."

Oh, I guess I should add that the problem may only be O(n), but the function may be poorly written and be O(n^3). That would be something we would, most likely, be able to help correct.

-fixed-

Oh, I'm disappointed. I don't know that service. I thought it was a routine you'd written. BTW: You're right -- don't post PEAR code here! You'd probably run out of chars for the post anyway.

-fixed-

If it doesn't contain personal information, could you post your solution here for others to see?

Been busy, but apparently I got my base crossed. Seems like I had in the back of my head O(n log(n)) instead of O(e^n) which is obviously what came out of my head. Anyway, there's a bit about it at http://www.leepoint.net/notes-java/a...-oh/bigoh.html which is where I found the reminder.

please Do Not Edit Original Post When Question Has Been Answered