We report findings that help us better understand the difficulty of tasks which involve information seeking, retrieving, gathering, and use. We examined the data gathered from two interactive information retrieval user studies on how users' perception of task difficulty changes before and after searching for information to solve tasks, and how the difficulty of tasks relates with users' background, previous experience with the tasks, and knowledge of the task topics, etc. The two studies employed carefully designed tasks with different types along several dimensions: task structure (subtasks being dependent upon or parallel with each other), task goal in quality (being specific or amorphous), and naming (being named or unnamed). It was found that while in some types of tasks, users' perceptions of task difficulty did not change before and after working on the tasks, in others, this did, either increasing or decreasing. Specifically, in the dependent-structured task, this did not change. In the parallel-structured or specific/named task, it decreased. In the amorphous/unnamed task, it increased. We also found that users' background factors do not normally correlate with their perceived task difficulty, or perceived difficulty change. In addition to helping understand the dynamic and complex nature of task difficulty, our findings have implications for system design that can provide assistance to users with their search and task solving strategies.