Time Analysis--Just Once!

• Let n be the number of symbols on the input

• Time spent reading characters: <=2n

• Time spent evaluating: <=n

• Number of push operations: <=3n

• Number of pop operations: <=3n. Ask yourselves: why?

• Total: <=9n, i.e. O(n)

Previous slide

Next slide

Back to first slide

View graphic version