Determining the Time and Space Complexity-CodePudding

I find this topic confusing and I am new to these terms.

I have a class like this:

public class Class1
{
    private IDictionary<int, double> Dictionary1;
    private List<double> pairList;

    public int Func1()
    {
        double rand = random.Next();
        int index = 0;

        foreach (var pairs in Dictionary1)
        {
            if (something)
            {
                // do sth.
            }
            index  ;
        }
        return 0;
    }


    public void Func2(List<KeyValuePair<string, string>> pairList)
    {
        foreach (var pair in pairList)
        {
            if (Dictionary1.TryGetValue(pair.Key, out double oldValue))
            {
                 //do something
            }
            Dictionary1.Add(new KeyValuePair<int, double>(pair.Key, pair.Value));
        }
    }
}

Question 1:

The time complexity is O(n) for this, right? If I use a binary search (O(logn)) instead of the foreach loop the func1, it would still be O(n) since we're considering the worst case. So, would that transformation be useless in the terms of time complexity?

Question 2:

What is the space complexity here and how is it calculated?

Question 3:

I know it is silly but I have to ask: Does the main program affect these calculations? Like I can also have for loops or other things for testing the main() functions, should I also add them to the calculations?

CodePudding user response：

Answer 1:
Yes, the time complexity for both Func1 and Func2 is O(n), with n being the number of items Dictionary1 or in pairList respectively.
Since the worst case of binary search is O(log(n)) it would decrease your time complexity for Func1. Keep in mind, that your list has to be sorted for a binary search to work, so that might add additional complexity.
However, if your main method calls both functions, it would still have a complexity of O(n). No matter what complexity Func1 has.
So you might consider it "useless" in terms of complexity. But an optimization of Func1 would still reduce the time it takes to compute main. Just because it doesn't reduce your time complexity, it doesn't mean, that your optimization is worthless.

Answer 2:
Space complexity describes the memory that is needed during computation, instead of the computing time. Basically, it is determined by the amount of additional variables that need to be created.
So to determine the complexity of Func1, it depends on what your // do sth. does.
I am not sure about this, but i think the space complexity of Func2 would be O(n), because it increses the size of your Dictionary1 by the amount of items in pairList. Again, the complexity might be increased by the content of //do something.

Answer 3:
It depends on what you want to calculate your complexity for. If you want to calculate the complexity of Func1 and Func2, it doesn't matter what happens in main. However, if you want to calculate the complexity of main, it is definitely important. Lets say, your main contains something like this:

for (int i = 0; i < pairList.Count; i  )
{
    Func1();
    Func2();
}

Since you have your functions of complexity O(n) inside of a loop, that loops n times, the time complexity of main is now O(n²). But this doesn't affect the complexity of Func1 and Func2 itself.