TIME COMPLEXITY Solution:

FC of Line 1: A statement
Rule 1: for-loops =1
FC of Line 2: Three statements. Initialization + Condition +
The running time for a for loop is at most the running time of Change of State
the statements inside the for loop (including tests) times the = Initialization is always 1
number of iterations. Condition is the difference of condition
and initialization plus the maximum number of comparison/s
Rule 2: Nested for-loops Change of state is one less than the
condition
Analyze these inside out. The total running time of a = 1 + ((n-1)+2) + (((n-1)+2) -1)
statement inside a group of nested for is the running time of = 1 + (n+1) + n
the statement multiplied by the product of the sizes of all the = 2n + 2
for loops. FC of Line 3: Open curly brace is not treated as a statement,
so no frequency count.
Rule 3: Consecutive Statements =0
FC of Line 4: One statement but repeated by the number of
These just add, which means that the maximum is the one times the condition is true.
that counts. =1*n
=n
Rule 4: if-else Statements FC of Line 5: Close curly brace is executed, so it is considered
as a statement.
For the fragment: =1
if(cond) FC of Line 6: A statement
S1; =1
else S2;
TFC = sum of all the FC from Line 1 to Line 6
the running time of an if/else statement is never more than
= 1 + (2n+ 2) + 0 + n + 1 + 1
the running time of the test plus the larger of the running
times of S1 and S2. TFC = 3n + 5
Big-O = the term (variable) with the highest degree
Problem: Determine the Total Frequency Count (TFC) and the Big-O = O(n)
corresponding Big-O notation for the code segment below.
Line 1 x = 500;
Line 2 for (i = 1; i <= n; i++) Cascading Loops: Compute the TFC and Big-O
Line 3 {
Line 4 x = x + i; Analysis: Cascading loops are loops outside a loop.
Line 5 }
Each loop is independent of the other. The strategy in
Line 6 System.out.println(x);
solving this problem is to compute the FC of each loop
and thereafter add them all up to arrive at the TFC. The 1) = k+1
term (variable) with the highest degree will be used for } =1
determining the Big-O. =1

Solution: FCc = 4k + 7
Program Segment Frequency Count Note: at worst-running time complexity, n, m and k can
Solution reach positive infinity, so (n=m=k)
for(a = 1; a <= n; a++) = 1 + (n-1+2) + ((n-
1+2)-1) = 2n+2 TFC = FCa + FCb + FCc
{ = (4n + 3) + (4m – 1) + (4k + 7)
statement1; = 1 * ((n-1+2)- = (4n + 3) + (4n – 1) + (4n + 7)
1) =n TFC = 12n + 9
statement2; = 1 * ((n-1+2)-
1) =n Big-O = O(n)
} =
1 =1
Evaluation of Expression
FCa = 4n + 3
Expression is made up of operands, operators and delimiters.
for(b = 1; b < m; b++) = 1 + (m-1+1) + ((m- Example:
1+1)-1) = 2m
{ X = 8 / 4 * 3 -5 * 6 + (7 - 2 * 9 % 2 ^ 3) + 8 * 9; //using
statement3; = 1 * ((m-1+1)-1) constants as operands and arithmetic operators.
= m-1 Y = A / B * C - D * E + (F - G * H % I ^ C) + A * H; // using
statement4; = 1 * ((m-1+1)-1) variables as operands and arithmetic operators
= m-1
} = Operands can be any legal variable names or constants in
1 =1 programming languages.

Operations are described by operators:

FCb = 4m - 1
 Basic arithmetic operators: +, -, *, /, %, ^
for(c = k; c > = 0; c --) = 1 + (k-0+2) + ((k-
0+2)-1) = 2k+4  Unary operators: - +
{  Relational operators: ==, >, <, >=, <=
statement5; = 1 * ((k-0+2)-
1) = k+1 Our concern: how the expressions are evaluated
statement6; = 1 * ((k-0+2)-
Three forms used for binary operators (requiring at 2 2. Put the # at the end of the expression (E). # simply
operands): means "nothing follows"

 Infix : <Operand1><Operator><Operand2> : (5 3. PUSH # in the STACK

+ 3) : Operator is in between both operands
4. Get the token form E and save it as X
 Prefix: <Operator> <Operand1><Operand2> :+5
5. Do the three checks:
3 : Operator is at the front of both operands
5.1 if X is an operand, print in the OUTPUT; else
 Postfix: <Operand1><Operand2><Operator> :5 5.2 if X is a ) then POP and print operators in the
3+ : Operator is at the end of both operands OUTPUT until (, then discard (; else
5.3 while ISP(Y) >= ICP(X), POP and print operators in
Note:
the OUTPUT;
 Infix is the human way of evaluating expressions. else PUSH X

 This is how our math teachers taught us and it is prone 6. Go back to step 4 while X is not # else go to step 7
to mistakes!
7. If STACK is not empty, POP and print operators in the
 MDAS or PEMDAS Rule IS NOT A RULE!!! This is one OUTPUT while not #.
reason for the erroneous computations. The proper
IN-Stack Priority (ISP) – The priority of the operator as an
rule should be The Precedence and Associativity Rule
element of the stack.
of Operators, which include Arithmetic, Relational and
IN-Coming Priority (ICP) – The priority of the operator as
Logical operators.
current token.
 Furthermore, creating a program to evaluate infix will
SYMBOL ISP (Y) ICP (X)
prove to be very challenging and ambiguous.
) -- -- closed
 So, Infix form should be transformed to either Prefix or
parenthesis
Postfix for a 1-D array implementation to be effective
^ 4 4 raised to
(consistently achieving the right output)
operator in this topic (not the bitwise XOR operator)
 Prefix has a higher TFC than Postfix. *, /, % 2 2
multiplication, division, modulo
 The compiler accepts expressions and produce correct +, - 1 1 addition,
result by reworking the expressions into postfix form. subtraction
Conversion from Infix to Postfix using STACKS ( 0 5 open
parenthesis
Algorithm converting infix form to postfix using stacks. # -1 -1 nothing
1. Create a table with 3 columns. Column1 for TOKEN (X), follows
Column2 for STACK(Y), Column3 OUTPUT
  Note: ISP and ICP values can be adjusted to include {
other operators such as relational and logical while STAK[top] != ‘#’
operators following the Precedence and Associativity {
Rule of operators. POP(Y);
print(Y);
Sample Code snippet:
}
void POSTFIX(expression E) }
token X ,Y;
xample:

STACK[0] = ‘#’; top = 0;

X= nexttoken(E); //takes the first token and remove it from
E = 8 / 4 * 3 -5 * 6 + (7 - 2 * 9 % 2 ^ 3) + 8 * 9#
the original expression.
while (X != ‘#’)
{
if (x is an operand print(x); TOKEN (X) STACK (Y) OUTPUT (POSTFIX)
else (if x ==‘)’ 8 # 8
{//unstack until ‘(’
while STACK[top] != ‘(’ / #/ 8
{ 4 #/ 84
POP(Y);
printf(Y); * #* 84/
} 3 #* 84/3
pop(y); //delete ‘(’
} - #- 84/3*
else
5 #- 84/3*5
{
while ISP[STACK[top]] >= ICP[X] * #-* 84/3*5
{
6 #-* 84/3*56
POP(Y);
print(Y); + #+ 84/3*56*-
}
( #+( 84/3*56*-
PUSH(X);
} 7 #+( 84/3*56*-7
X = nexttoken(E);
} - #+(- 84/3*56*-7
if(!empty(STACK)) 2 #+(- 84/3*56*-72
* #+(-* 84/3*56*-72 2 3 * 30 - 7 18 8 % - + 8 9 * +

9 #+(-* 84/3*56*-729 2 3 * 30 - 7 18 8 % - + 72 + //repeat

% #+(-% 84/3*56*-729* 2 3 * 30 - 7 18 8 % - + 72 +

2 #+(-% 84/3*56*-729*2 6 30 - 7 18 8 % - + 72 +

^ #+(-%^ 84/3*56*-729*2 6 30 - 7 2 - + 72 + //repeat

3 #+(-%^ 84/3*56*-729*23 6 30 - 7 2 - + 72 +

) #+ 84/3*56*-729*23^%- -24 7 2 - + 72 +

+ #+ 84/3*56*-729*23^%-+ -24 5 + 72 + //repeat

8 #+ 84/3*56*-729*23^%-+8 -24 5 + 72 +

* #+* 84/3*56*-729*23^%-+8 -19 72+ //repeat

9 #+* 84/3*56*-729*23^%-+89 53 //Final Answer

# (nothing follows) # (nothing follows) 8 4 / 3 * 5 6 * - 7 2 9 *

23^%-+89*+

E=84/3*56*-729*23^%-+89*+

Store the POSTFIX of E in a 1-D array: 8 4 / 3 * 5 6 * - 7 2 9 *

23^%-+89*+

Loop from left to right processing only POSTFIX form until no

operator is left to get the answer.

Simulation

84/3*56*-729*23^%-+89*+

23*56*-729*23^%-+89*+

2 3 * 30 - 7 2 9 * 2 3 ^ % - + 8 9 * +

2 3 * 30 - 7 18 2 3 ^ % - + 8 9 * +