Someone help me with this.

Question

Help me understand Time Complexity and storage complexity. Posts here are too hard for me .

Answer 1

Time complexity is calculated based on the number of basic operations done by the computer.
A linear search for a number x in an array of n numbers has an aproximate complexity of O(n), because it will do like n*r operations before it finds out whether x is in the array or not. Here, r is a ratio that may be small (like 1/10 if x is found after comparing it with a tenth of the elements in the array) or maybe larger, but anyway it's assumed that r is like 1/2 or something, and if n is a huge number, n/2 is still huge. Because of this, the complexity is simplified to O(n). Binary search has a lower complexity (like O(lg(n)) ). I can't explain why in detail, but do a few binary searches in your head and you'll realise what's up. In the end, there are around lg(n) operations. Now, even though we tend to simplify things, we can't always do that.
If we have
loop 1:
for (i=0; i<n; i++)
{
//do 100 operations
}
and
loop 2:
for (i=0; i<n; i++)
{
//do 1 operation
}
then loop 1 will consume way more time

Answer 2

...because loop 1 has 100 operations*100 loop runs+100 incrementations of i+(i think)100 comparisons of i and n, while loop 2 has 1 operation*100 runs+all the other stuff

Answer 3

Storage complexity is about how much memory the computer uses because of a certain instruction. I can't explain that one in depth, you should try searching about it at stack overflow, on youtube, wikipedia etc

Answer 4

One more thing: sites that offer information regarding standard library functions specify the time complexity of the functions.

Answer 5

When comparing different ways to complete certain tasks, you may find advanced math very helpful, specifically calculating the limit of functions/sequences, like limit of (f(x)/g(x)) when x approaches infinity. Here, the function f may represent the time complexity of one way to solve a problem, and g the time complexity of another way. If this limit evaluates to a number smaller than 1, the first way is faster. Otherwise, the second one is faster.

Answer 6

Alex thanks for the explaination. binary search tree is O (log n ) because it depends totally on the height of tree and height of the tree is n . I just have another doubt , what is the difference between O( (some complexity ) ) and ●(symbols theta ) ((some complexity ))?

Answer 7

idk, never encountered that
ask google maybe