O(n) denotes linear time complexity, where the execution time increases directly with the input size, while O(log n) indicates logarithmic time complexity, which grows more slowly as the input size increases. O(n) is common in algorithms that require a complete traversal of data, like searching through an unsorted list, whereas O(log n) is typical in algorithms that divide the problem space, such as binary search on a sorted array.