Question

The answer of this question has been attached, and the questions that should be answered is also attached.

The question was:

Write pseudocode for a brute force algorithm for each of the following, and determine its time and space complexity.

1. Determine whether a given Boolean expression is satisfiable.

Notes:

1. A.) A Boolean expression is one written using only the three Python connectives (and, or, not), and variables ranging over True and False, and parentheses.
2. B.) A Boolean expression is satisfiableif there is a substitution of values for its variables that makes it true.
3. C.) Operations available:

1. a.) vars(E) gives a list of the variables occurring in Boolean Expression E
2. b.)val(E) gives the value of a ground Boolean expression (that is, one written with True,False, and, or, not and parentheses)
3. c.) sub(V,X,E) returns the result of substituting value V for variable X in expression E
4. d.) basic list operations are available

Please check the attachment file.

The problem is that I don't know how to calculate the time and space complexty for the algorithm that attached, and I don't know how to determine the size of input and the number of operation of this algorithm to find out the time comlexity?

Also, how can I prove that answers!

Fune isSatsfiable (E) if Len (L)-O else Yetum (iSatsfable (sub (true,V, E))or isSatisfable (sub (false, v, E) D what is He time and Space Corplexity fr this 2) what is the Size of Impuk ? ② what is number of operation ? Aj How to determine the time Covmple h of this agoritles ?

Answer 1

Time Complexity: Assume there are N elements in the array. Let's call this array A.
Suppose counting starts from 1 and goes till N.
So, A[1] = first element
A[2] = second element and so on....

In brute force, you'll pick one element and compare it with all the other elements and will perform either of 2 options- swap or nothing. No matter what you do, you'll compare 1 element with rest of the elements i.e N-1.

So, for A[1], check for all elements.
for A[2], check for all elements.
and so on....

So it will be N*N = O(N^2).