4 ms·

Well it can get hard sometimes. Ill assume you dont get the basics and try to explain them to you. For the sake of simplicity, it's just all about getting a ba

Well it can get hard sometimes. Ill assume you dont get the basics and try to explain them to you. For the sake of simplicity, it's just all about getting a ballpark of the resources an algorithm take (often time, can be memory too) without taking into account the specificity of the machine the program runs into. Let say the algorithm is x+1, x being a number. Now, you can certainly tell that whatever is the computer, it should be fast right. It's O(1). 1 here means, we know it takes one number (x) to compute the result. Wait you gonna say, it takes 2 actually, x and 1. Well yeah, it's 2 then. But it's always gonna be 2. Its not gonna be 3, its not gonna be 4, its gonna be 2, always. Lets take another example of O(1): x+y+1. How many operations here? 3. Always 3. So its always a constant number of operation and we call that O(1). Now let say we have the following algorithm: result = 0, for each x in L: result += x How many operations? Well now, it depends on the size of L and if L is big, its gonna take a while to compute. Its not a constant anymore. We call that O(N). N here means: the ballpark is: the size of a list. Its not a constant number of operation, its a number of operation the size of a list. Now, say you have: result = 0, for each i in L: for each j in M: result += i-j Whats the ballpark here? The size of a list multiplied by the size of another list. So O(N*N) or O(N2). Now youll find some algorithm runs at O(log N) on average for example. It means its in the ballpark of the size of a list but...no; weve been able to prove that its quite better than that. Say you search in a binary tree, on average, chances are you wont visit all nodes. On average the ballpark is better than the size of a list. Its log N. Why log? Because its a binary tree and binary trees divide by 2 the size of the remaining list after each step or operation.

quadcore 5y ago
result = 0 for each x in L: result += x for each x in M: result -= x (Loops arent nested here but done sequentially) Whats the ballpark? O(2N) you might say. Nah, its like saying that x+1 is O(2), you re not giving me the ballpark here. What matters is how fast it grows when we put in more inputs. We dont care how many operations there is exactly. It's O(N). Think of it like, whatever are the details, we have traversed one list, the concatenation of L and M. Weve just traversed lists sequentially, its in the ballpark of traversing one (think of it as a big one if you need too) list. O(N).

quadcore 5y ago

result = 0 for each x in L: result += x for each x in M: result -= x (Loops arent nested here but done sequentially) Whats the ballpark? O(2N) you might say. Nah, its like saying that x+1 is O(2), you re not giving me the ballpark here. What matters is how fast it grows when we put in more inputs. We dont care how many operations there is exactly. It's O(N). Think of it like, whatever are the details, we have traversed one list, the concatenation of L and M. Weve just traversed lists sequentially, its in the ballpark of traversing one (think of it as a big one if you need too) list. O(N).