In this paper, the time complexities of some robust discrete optimization problems are described. After stating the basic concepts, problems and definitions, robust variants of the shortest path, smallest spanning tree and knapsack packing problems are examined. The concepts of classes P and NP as well as P-hard and NP-hard problems are introduced. The aforementioned problems are studied with certain limitations compared to their conventional variants. A layered network is defined and it is shown that the absolute robust and robust deviation shortest path problems are weakly NP-hard even in layered networks of width two and with only two scenarios. After proving these statements, algorithms for the layered network problem for each are given. These problems are strongly NP-hard when the number of scenarios is not limited. After these claims have been proven, the next chapter introduces the concept of a grid graph. The absolute minimum spanning tree problem is proven to be weakly NP-hard on a fairly restricted grid graph with only two scenarios. An algorithm is given that solves the problem in pseudo-polynomial time for a grid graph and a bounded number of scenarios. Then it is proven that the absolute minimum spanning tree problem is strongly NP-hard when the number of scenarios is unbounded. The second to last chapter proves that the absolute robust knapsack problem is strongly NP-hard on an unlimited number of scenarios and the corresponding algorithm is given. The last chapter contains a concrete implementation of an algorithm that solves the absolute robust shortest path problem in the Ruby programming language with associated examples.